ST310 Course Project

The aim of this project is to demonstrate the use of machine learning techniques learnt in the ST310 Machine Learning module. We rely on both linear (Logistic Regression) and non-linear methods (Random Forests and Gradient Boosted Decision Trees) for a classification problem.

Remark: If executing this notebooks as a .Rmd file, ensure that all libraries are installed and that the cells are executed in sequential order.

Dataset

We have obtained data from the Kaggle March Tabular Playground competition. The data consists of anonymised features, which correspond to a binary outcome variable; in other words the task is a classification problem. Although the data is anonymised, we are told that it is based on a real dataset that deals with predicting the amount of an insurance claim.

We consider the ROC-AUC metric (Receiving Operator Characteristic Area Under the Curve), and accuracy metric. Given the problem is indirectly one related to insurance, the modelling outcome of interest is not only to obtain the correct predictions (accuracy) , but also accurate probabilities, which is what the AUC metric measures.The test accuracy

library(tidyverse)
library(ggplot2)
library(tidymodels)
library(xgboost)
library(catboost)
library(tidyverse)
library(broom)
library(ggplot2)
library(arm)
library(car) #outlier
library(tidyr)
library(glmnet)
library(caret)
library(tidymodels)
library(pROC)
library(randomForest)
library(e1071)
library(arm)
library(data.table)
df <- read.csv(file = "../data/train.csv")

The dataset consists of 30 features, 19 categorical variables and 11 numerical variables., and a binary outcome variable target. We will need to process these categorical variables in some manner, which we shall consider in the subsequent section.

A challenge is that we have no specific domain knowledge about the meaning of particular features, and whether they may be useful. Nonetheless, we can resort to model interpretability methods (Christoph Molnar 2019) - in the linear case, we can examine coefficients and their statistical significance, and in the case of tree-based models, we can utilise feature importances, partial dependence plots, and shapley values.

Preprocessing

We first remove the first column id, which represents an unique identifier for each observation. We then convert the first 19 columns, which are categorical variables into the factor data type in R, To reduce computational time, we subsample 4000 observations from the complete dataset of 300,000 observations. For our subsequent analysis, we will use only this subsample of 4000 observations, although the approaches can be extended to a larger dataset given greater computational resources. We further partition the 4000 observations, into a train set of 3000 observations and a test set of 1000 observations. All training and tuning are performed on the training data, and we will consider model performance on the test set performance scores.

rownames(df) = df$id
df = df[,-1] # remove id column
cat_feats = 1:19 # the first 19 columns are categorical 
cont_feats <- 20:30 # and the next 11 are continuous
df[,cat_feats] <- lapply(df[,cat_feats], as.factor)
df$target <- as.factor(df$target)
# subsample the data for faster model imputation
set.seed(1)
sam = sample(1:nrow(df), 4000)
df_sample = df[sam,]
# Partition data into train and test; test will be our oos data
set.seed(1)
df_split <- initial_split(df_sample, prop = 3/4)
df_train <- training(df_split)
df_test <- testing(df_split)

Exploratory Data Analysis

Univariate EDA

We observe that the univariate distributions of the continuous variables are all multi-modal and non-normal, but they are all normalised to the range of \([0, 1]\).

df %>% pivot_longer(cols = starts_with("cont"), names_to  = "cont") %>% 
   ggplot(aes(x = value))+
   geom_histogram(bins = 100, alpha = 0.85)+
   ggtitle("Continuous features distribution")+
   facet_wrap(cont~.,scales = "free") +
   theme_minimal()

From the distributions of categorical variables, we see that there are variables with substantially more observations in one category, and also variables with a high number of (\(>50\)) categories, which will be an issue to address in our preprocessing step.

df %>% pivot_longer(cols = contains(c("cat")), names_to  = "cat") %>% 
   ggplot(aes(x = value))+
   geom_bar(alpha = 0.85)+
   ggtitle("Categorical features distribution")+
   facet_wrap(cat~.,scales = "free")+
   theme_minimal()

Bivariate EDA

We group the continuous variables by the target and plot them as boxplots to check for any obvious differences discernible by eye. From the plots, claims with target == 1 have lower values of cont3 on average (median) than claims with target == 0, hence we would expect a negative relationship between cont3 and target. Claims with target=1 also have a higher median value of cont4 than claims with target == 0. In addition, we see a group of observations at the tail ends for cont0, cont5, cont7, cont8, cont9, cont10, which may be indicative of outliers. This will be addressed in a subsequent section.

cont.stacked <- gather(data=df[, c(cont_feats, 31)],-target,key="var",value="value")
p.cont <- ggplot(cont.stacked,aes(x=target,y=value),fill=factor(value)) + geom_boxplot() + coord_flip() + facet_wrap(~var, scales="free_x")
p.cont

For categorical variables, we use stacked bar plots to show the percentages of observations in each category that correspond to target == 0 and target == 1 respectively. A much larger proportion of claims with cat13 == B appear to be associated with target == 1 compared to cat13 == A. On the other hand, a much larger percentage of claims correspond to target == 0 if cat18 is A or B, than if cat18 is C or D.

g1 <- c(1:10,31)
g2 <- c(11:19,31)
cate.stacked1 <- gather(data=df[,g1],-target,key="var",value="value")
p.cate1 <- ggplot(cate.stacked1,aes(x=value,fill=target)) + geom_bar(position="fill") + scale_y_continuous(name = "Within group Percentage", labels = scales::percent) + facet_wrap(~var, scales="free_x")
cate.stacked2 <- gather(data=df[,g2],-target,key="var",value="value")
p.cate2 <- ggplot(cate.stacked2,aes(x=value,fill=target)) + geom_bar(position="fill") + scale_y_continuous(name = "Within group Percentage", labels = scales::percent) + facet_wrap(~var, scales="free_x")
p.cate1

p.cate2

We also inspect the correlation matrix for our continuous variables. There seems to be a cluster of variables - cont1, cont2, cont8 - that are highly correlated with each other. This could lead to problems with multicollinearity when using linear models.

df_num <- df[, cont_feats]
cor_matrix <- cor(df_num)
heatmap(cor_matrix)

Finally, we use Principal Components Analysis (PCA) as a means to visualise the data in low-dimension, to determine if there are any explicitly discernible trends. By eye, the classes do not appear to be linearly seperable - which suggest a non-linear method may be more effective. There do not appear to be any significant difference in the PCA representations for each class.

pcs <- prcomp(df[,cont_feats])
set.seed(2021)
ind <- sample(1:dim(df)[1], 20000)
sample <- data.frame(pcs$x[ind,1], pcs$x[ind,2], df[ind, "target"])
names(sample) = c("pc1", "pc2", "y")
ggplot(sample) + geom_jitter(aes(x = pc1, y = pc2, colour = factor(y)),alpha=0.7) + ggtitle('Principal Components')

Source: https://statsandr.com/blog/outliers-detection-in-r/

Modelling

We first consider a naive ‘basline,’ in which we let all predicted labels equal 0 or 1 (whichever leads to the greater accuracy; the accuracy would be the greater of either \(\hat{y}\) or \(1 - \hat{y}\)). In this case, the greater accuracy of \(0.745\) would be obtained if we predict all labels as 0, which suggests the 1 class is less frequently occurring i.e. imbalanced classification. This illustrates the issue with the accuracy metric: we must compare our model accuracy with the naive accuracy and other appropriate benchmarks to prevent a misleading result, as our. On the other hand, predicting all 1s or 0s would result in the worst possible ROC-AUC score of \(0.5\).

# train-test
X_train = as.matrix(df_train[,grepl("cont", colnames(df_train))])
y_train = as.numeric(as.matrix(df_train$target))
X_test = as.matrix(df_test[,grepl("cont", colnames(df_train))])
y_test = as.numeric(as.matrix(df_test$target))
results = data.frame(train_acc = max(1 - mean(y_train), mean(y_train)),
                     train_auc = 0.5,
                     test_acc = max(1 - mean(y_test), mean(y_test)),
                     test_auc = 0.5,
                     row.names=c("naive")
                     )
results

Logistic Regression (Few Predictors)

As a baseline model, we build a simple logistic regression with a few predictors, which are selected from our exploratory data analysis to have discernible differences in target. These are cont3, cont4, cat13, cat18. We use the glm package to fit a logistic regression.

glm1 <- glm(target~cont3+cont4+cat13+cat18,data=df_train, family=binomial(link="logit"),control = list(maxit = 100))
summary(glm1)

Call:
glm(formula = target ~ cont3 + cont4 + cat13 + cat18, family = binomial(link = "logit"), 
    data = df_train, control = list(maxit = 100))

Deviance Residuals: 
    Min       1Q   Median       3Q      Max  
-1.5707  -0.6702  -0.6021   0.3931   2.0095  

Coefficients:
            Estimate Std. Error z value Pr(>|z|)    
(Intercept)  -1.4821     1.0756  -1.378  0.16824    
cont3        -0.6554     0.2276  -2.880  0.00398 ** 
cont4        -0.4772     0.2063  -2.313  0.02070 *  
cat13B        1.8681     0.3346   5.584 2.36e-08 ***
cat18B        0.5581     1.0714   0.521  0.60243    
cat18C        2.6081     1.0816   2.411  0.01590 *  
cat18D        2.4342     1.0805   2.253  0.02427 *  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 3406.6  on 2999  degrees of freedom
Residual deviance: 2962.8  on 2993  degrees of freedom
AIC: 2976.8

Number of Fisher Scoring iterations: 4

All four predictors are significant at 5% level, with the most significant predictors being… The coefficients of the dummy variables indicate the average difference between the log odds of that factor level group compared to the baseline level group. In our regression, the first category (A) of each categorical variable is taken as the baseline group. For example, the coefficient of cat13b implies the following equation: \[\text{logit} P(\text{target}=1|\text{cat13b} = 1) – \text{logit} P(\text{target}=0|\text{cat13b} = 1) = 1.8681. \] In words, this means that claims with cat13b = 1 have 33% higher log odds of target=1 than claims with [catA]. However, we can only assert that there is some association - in this case it is statistically significant relationship with the p-value being 2.36e-08 - between the presence of the variable cat13b = 1 and the target being 1, but not whether there is a causation; in particular, given the lack of knowledge of what the variable represents, we cannot form any meaningful hypothesis.

To interpret the coefficients of the continuous variables, risk ratios need to be calculated using specific pairs of values of the predictors. The non-linearity of the logistic function means that a change of one unit in the value of a predictor is not the same across the range of the predictor.

pred_train <- predict(glm1, df_train, type="response")
pred_test <- predict(glm1, df_test, type="response")

diagnosis <- function(train_pred, test_pred, train_true, test_true){
  train_classes <- ifelse(train_pred > 0.5, 1,0)
  test_classes <- ifelse(test_pred > 0.5, 1,0)
  acc1 <- mean(train_classes == train_true)
  auc1 <- auc(roc(train_true, train_pred))
  acc2 <- mean(test_classes == test_true)
  auc2 <- auc(roc(test_true, test_pred))
  data.frame(train_acc=acc1, train_auc=auc1, test_acc = acc2, test_auc=auc2)
}

results["glm-small",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-small",]

SGD

To fulfill the project requirements, we demonstrate a `from scratch’ Stochastic Gradient Descent routine for logistic regression. The deriviation follows (Hastie, T. and Tibshirani, R. and Friedman, J.H. 2009, 120–26)

The logistic loss with a \(\mathcal{L}^{2}\) penalty is given by:

\[l(\boldsymbol{\beta}) = -\sum_{i = 1}^{N} y_{i} log(p(x_{i} ; \boldsymbol{\beta})) + (1 - y_{i}) log(1 - p(x_{i} ; \boldsymbol{\beta})) = \sum_{i = 1}^{N} \left [ y_{i}log \left (\frac{p(x_{i} ; \boldsymbol{\beta})}{1 - p(x_{i} ; \boldsymbol{\beta})} \right) + log(1 - p(x_{i} ; \boldsymbol{\beta})) \right ]\]

\[ l(\boldsymbol{\beta})= -\sum_{i = 1}^{N}\left [y_{i} \boldsymbol{\beta}^{T} x_{i} - log(1 + exp(\boldsymbol{\beta}^{T}x_{i})) \right ]\] Then with the inclusion of the reularisation term:

\[ l(\boldsymbol{\beta}) = -\sum_{i = 1}^{N} \left [y_{i} \boldsymbol{\beta}^{T} x_{i} - log(1 + exp(\boldsymbol{\beta}^{T}x_{i})) \right ] - \lambda \boldsymbol{\beta}^{T} \boldsymbol{\beta}\]

The gradient is given by:

\[\nabla(\boldsymbol{\beta}) = -\sum_{i = 1}^{N} \left [ y_{i} x_{i} - \frac{x_{i}exp(\boldsymbol{\beta}^{T} x_{i})}{1 + exp(\boldsymbol{\beta}^{T} x_{i})} \right] - \lambda 2\boldsymbol{\beta}\]

We use the Barzilai-Borwein method (Murphy, Kevin P 2012, 444–45) to determine the step size.

# binary crossentropy / log-loss
log_loss <- function(x, y, betas, lambda){
  logits <- x %*% betas
  - (t(y) %*% logits - sum(log(1 + exp(logits))) + lambda * t(betas) %*% betas) / dim(x)[1]
}

# logistic regression gradients
gradients <- function(x, y, betas, lambda){
  logits <- x %*% betas
  - (t(x) %*% (y - exp(logits)/(1 + exp(logits)))) - lambda *2 * betas / dim(x)[1]
}

p = dim(X_train)[2]

lambda = 0
n_iters <- 100
init_step_size <- 1e-6

set.seed(2021)
beta_init <- matrix(rnorm(p),nrow=p)
beta_path <- matrix(rep(0, n_iters * p), nrow = n_iters, ncol=p)
beta_path[1,] = beta_init

last_grad <- grad <- gradients(X_train, y_train, beta_path[1,], lambda)
beta_path[2,] = beta_init - init_step_size * grad
grad <- gradients(X_train, y_train, beta_path[2,], lambda)

losses <- rep(0, n_iters)

for (i in 3:n_iters){
    step_size <- as.numeric(t(beta_path[i - 1,] - beta_path[i - 2,]) %*% (grad - last_grad) / 
                    (t(grad - last_grad) %*% (grad - last_grad)))
    beta_path[i,] <- beta_path[i - 1,] - step_size * grad
    last_grad <- grad
    grad <- gradients(X_train, y_train, beta_path[i, ], lambda)
    losses[i] <- log_loss(X_train, y_train, beta_path[i,], lambda)
}
ggplot(data.frame(step = 3:n_iters, loss=losses[3:n_iters])) + 
  geom_line(aes(x = step, y = loss)) +
  ggtitle("Binary Crossentropy vs. Iterations")

pred_train <- as.numeric(1 / (1 + exp(-X_train %*% beta_path[100,])))
pred_test <- as.numeric(1 / (1 + exp(-X_test %*% beta_path[100,])))
results["sgd",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["sgd",]

Logistic Regression (All Predictors)

We now run a logistic regression using all variables, using the glm package.

glm2 <- glm(target~., data=df_train, family=binomial(link="logit"), 
            control = list(maxit = 100))
pred_train <- predict(glm2, df_train, type="response")
glm2$xlevels = lapply(df[,cat_feats], levels)
pred_test <- predict(glm2, df_test, type="response")
results["glm-full",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-full",]
anova(glm1, glm2, test="Chisq")
Analysis of Deviance Table

Model 1: target ~ cont3 + cont4 + cat13 + cat18
Model 2: target ~ cat0 + cat1 + cat2 + cat3 + cat4 + cat5 + cat6 + cat7 + 
    cat8 + cat9 + cat10 + cat11 + cat12 + cat13 + cat14 + cat15 + 
    cat16 + cat17 + cat18 + cont0 + cont1 + cont2 + cont3 + cont4 + 
    cont5 + cont6 + cont7 + cont8 + cont9 + cont10
  Resid. Df Resid. Dev  Df Deviance Pr(>Chi)
1      2993       2963                      
2      2552      42964 441   -40001         

Outlier Detection

At this stage, we seek to remove outliers spotted in the bivariate plots in our exploratory analysis for cont0, cont5, cont7, cont8, cont9 and cont10. To investigate this, we identified observations that lie at the extreme percentiles of these variables. Using the Hampel filter, which considers points lying outside the median plus or minus 3 mean absolute deviations as outliers, more than 200 observations per variable were classified as such. This suggests that these may not be outliers but that the distribution is just heavy-tailed. Without further information on the reasonable scale of values that individual variables can take (along with the fact that they are all normalised), we find it challenging to clearly identify outliers through descriptive statistics and decide not to exclude any such points using this approach. We will proceed to detect for outliers in another approach later on.

hampel_filter <- function(df){
   lower_bound <- median(df) - 3 * mad(df, constant = 1)
   upper_bound <- median(df) + 3 * mad(df, constant = 1)
   outlier_ind <- which(df < lower_bound | df > upper_bound)
   return(outlier_ind)
}
percentile_filter <- function(df, lq = 0.001, uq = 0.999){
   lower_bound <- quantile(df, lq)
   upper_bound <- quantile(df, uq)
   outlier_ind <- which(df < lower_bound | df > upper_bound)
   return(outlier_ind)
}
hampel_count <- function(x){length(hampel_filter(x))}
pct_count <- function(x){length(percentile_filter(x))}

outlier_counts <- data.frame(lapply(df_train[, cont_feats], hampel_count))
outlier_counts[2, ] <- data.frame(lapply(df_train[, cont_feats], pct_count))
outlier_counts

We attempt to detect outliers under a logistic regression. Formally, outliers are defined as observations with a response vector that is unusual conditional on covariates. They are formally identified through studentized residuals. Intuitively, outliers have large residuals and we can formally test (by looking at the Bonferroni–adjusted p-values) if these residuals are significantly larger than the other observations. We use the outlierTest function from the car to determine the outliers from the glm model.

Observations that are far from the average covariate pattern are considered to have high leverage and can be measured using the hat value. Here, there are many points with high leverage.

outlierTest(glm2)
outliers <- as.numeric(names(outlierTest(glm2)$p))

Finally, we measure for influence, which is an observation that is an outlier and have high leverage. These are likely to influence the regression coefficients and influence can be thought of as the product of leverage and outlier. Here, we plot studentised residuals against hat-values with the size of a circle being proportional to the Cook’s distance of an observation- a measure of influence.

influenceIndexPlot(glm2, vars = "hat")

influencePlot(glm2)

Here, we observe that there are a number of observations with high influence - outliers with high leverage. Thus, we remove these observations and compare the performance of our updated model with the original model.

In the later models, we will also exclude the same outliers.

influencers <- as.numeric(rownames(influencePlot(glm2)))
glm2_influencers <- update(glm2, subset = c(-influencers))
glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred
glm2_outliers <- update(glm2, subset = c(-outliers))
glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred

Logistic + Ridge

Given the issue of high dimensionality, we consider a regularised form of logistic regression. We use the glmnet package; in doing so we need to convert the data type into matrices.The glmnet package requires the data to be in a matrix data type, and hence we make the corresponding adjustment.

X_train = df_train[, -length(df_train)]
y_train <- df_train$target
X_test = df_test[, -length(df_test)]
y_test <- df_test$target
X_train = model.matrix(~., X_train)
X_test = model.matrix(~., X_test)

glm3 <- cv.glmnet(X_train, y_train, 
                  family="binomial"(link="logit"), alpha=0)
glm3

Call:  cv.glmnet(x = X_train, y = y_train, family = binomial(link = "logit"),      alpha = 0) 

Measure: GLM Deviance 

    Lambda Index Measure      SE Nonzero
min 0.1422    80  0.7846 0.01822     458
1se 0.3606    70  0.8010 0.01636     458
pred_train <- as.numeric(predict(glm3, X_train, type="response"))
pred_test <- as.numeric(predict(glm3, X_test, type="response"))
results["glm-ridge",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-ridge",]

Nonlinear Fit (Tree-based)

Random Forest

To improve performance, we draw on the usage of non-linear tree-based models, specifically random forests. Intuitively, a random forest averages different decision trees (known as bagging) so as to reduce the variance of individual trees.

control <- trainControl(method = "cv",
    number = 2,
    search = "grid")

ptm=proc.time()
set.seed(1)
rf1 <- train(target~.,
    data = df_train,
    method = "rf",
    metric = "Accuracy",
    trControl=control, 
    importance=T,
    maxnodes=128,
    ntree=64)
pred_train <- predict(rf1,df_train,type='prob')[,2]
pred_test <- predict(rf1, df_test, type='prob')[,2]
results["rf",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["rf", ]

The random forest has a test accuracy of 0.836 and a test AUC of 0.872, which is higher than the previous linear models. However, the train accuracy and AUC are significantly higher than the test performance, which suggest that there may be some degree of overfitting to the train data.

Random forests can be used to rank the importance of different features. Specifically, the x-axis is the Mean Decrease Accuracy, which reports how much accuracy the model loses when we exclude this variable. The more the accuracy falls by, the more important the particular variable is. Note here that for categorical variables, each level of the category is classified as a single variable. In this plot, we recorded the 30 most important variables.

We then run another random forest with the most important features. In doing so, we hope to reduce the degree of overfitting by reducing the complexity of the model. However, it does not make sense to drop some levels of a categorical variable while including the other levels. Hence, as long as a level is present in the top 30 features, we will include the entire category in our updated random forest model. This results in us keeping only 22 variables, from an initial 30.

Our reduced random forest has a slightly improved test accuracy and a slightly decreased test AUC. However, it does not solve the potential problem of overfitting as train performance is still significantly better than test performance. In fact, train performance on the reduced random forest is better than the random forest with a full set of variables - the reduced complexity of the model enabled it to have a lower bias on the training set.

XGBoost

For completeness, we also consider the xgboost library for gradient boosted decision trees. Gradient Boosted Decision Trees. The XGBoost package, introduced in (Chen, Tianqi and Guestrin, Carlos 2016) is a variant of Gradient Boosted Decision Trees (Hastie, T. and Tibshirani, R. and Friedman, J.H. 2009, 353–74)

dmy_train <- dummyVars("~.", data = df_train[,-length(df_train)])
dmy_test <- dummyVars("~.", data = df_test[,-length(df_test)])
X_train <- as.matrix(data.frame(predict(dmy_train,df_train)))
X_test <- as.matrix(data.frame(predict(dmy_test,df_test)))
y_train = as.integer(as.matrix(df_train$target))
y_test = as.integer(as.matrix(df_test$target))
bst <- xgboost(data = X_train, label=y_train, max_depth = 2, nround = 10, 
               verbose=0,
               objective='binary:logistic',
               eval_metric="logloss")

pred_train <- predict(bst, X_train, type="response")
pred_test <- predict(bst, X_test, type="response")
results["xgb",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["xgb",]

importance_matrix <- xgb.importance(model=bst)
xgb.plot.importance(importance_matrix)

# shapley values
xgboost::xgb.ggplot.shap.summary(X_test, model = bst, 
                                 target_class = 1, top_n = 20)  # Summary plot

CatBoost

We also consider briefly examine the catboost library for gradient boosted decision trees, given its popularity on machine learning competitions such as Kaggle. The CatBoost library has the advantage of learning a target encoding for categorical variables. From an implementation point of view, this may reduce the preprocessing that may be required.For details on CatBoost, refer to (Prokhorenkova, Liudmila and Gusev, Gleb and Vorobev, Aleksandr and Dorogush, Anna Veronika and Gulin, Andrey 2017)

X_train = df_train[,c(cat_feats, cont_feats)]
y_train = as.integer(df_train$target)
X_test = df_test[,c(cat_feats, cont_feats)]
y_test = as.integer(df_test$target)

pool <- catboost.load_pool(X_train, y_train, cat_features = cat_feats)
model <- catboost.train(pool, params=list(depth = 8, iterations = 10, 
                                          loss_function='Logloss', verbose=0))

pred_train <- catboost.predict(model, catboost.load_pool(X_train), prediction_type = 'Probability')
pred_test <- catboost.predict(model, catboost.load_pool(X_test), prediction_type = 'Probability')

data_shap_tree <- catboost.get_feature_importance(model, pool = pool,
                                                  type = "ShapValues")
data_shap_tree <- data.frame(data_shap_tree[, -ncol(data_shap_tree)]) 
names(data_shap_tree) = names(df[, c(cat_feats, cont_feats)])


ggplot(stack(data_shap_tree), aes(x = ind, y = values)) +
    geom_point(aes(color = values)) + coord_flip() + ggtitle("Shapely Values for each variable")


results["catboost",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["catboost",]
feat_importance <- catboost.get_feature_importance(model, pool)
importances <- data.frame(feat_importance[order(feat_importance, decreasing=FALSE),])
importances$features = rownames(importances)
names(importances) <- c("importance","features")
importances$features <- factor(importances$features, level=importances$features)
ggplot(importances, aes(x=importance, y=features)) + geom_bar(stat="identity")

Results

results

Bibliography

Chen, Tianqi and Guestrin, Carlos. 2016. “XGBoost: A Scalable Tree Boosting System.” https://arxiv.org/pdf/1603.02754.pdf.
Christoph Molnar. 2019. “Interpretable Machine Learning.” “https://christophm.github.io/interpretable-ml-book”.
Efron, Bradley and Hastie, Trevor. 2016. “Computer Age Statistical Inference.” Cambridge University Press.
Hastie, T. and Tibshirani, R. and Friedman, J.H. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer.
James, Gareth, Daniela Witten, Trevor Hastie, and Robert Tibshirani. 2017. “An Introduction To Statistical Learning.” Springer.
Murphy, Kevin P. 2012. “Machine Learning: A Probabilistic Perspective.” MIT Press. https://christophm.github.io/interpretable-ml-book.
Prokhorenkova, Liudmila and Gusev, Gleb and Vorobev, Aleksandr and Dorogush, Anna Veronika and Gulin, Andrey. 2017. “CatBoost: Unbiased Boosting With Categorical Features.” https://arxiv.org/pdf/1706.09516.pdf.
LS0tCnRpdGxlOiAiU1QzMTAgQ291cnNlIFByb2plY3QiCmF1dGhvcjogIkNocmlzIENoaWEsIE11biBGYWkgQ2hhbiwgWmhlbiBZZW4gQ2hhbiIKZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJWQvJW0vJXknKWAiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgaHRtbF9kb2N1bWVudDoKICAgIHRvYzogdHJ1ZQogICAgZGZfcHJpbnQ6IHBhZ2VkCiAgICBrZWVwX21kOiB0cnVlCiAgcGRmX2RvY3VtZW50OiBkZWZhdWx0CmhlYWRlci1pbmNsdWRlczoKLSBcdXNlcGFja2FnZSB7aHlwZXJyZWZ9Ci0gXGh5cGVyc2V0dXAge2NvbG9ybGlua3MgPSB0cnVlLCBsaW5rY29sb3IgPSBibHVlLCB1cmxjb2xvciA9IGJsdWV9CnJlZmVyZW5jZXM6Ci0gaWQ6IGhhc3RpZTIwMDllbGVtZW50cwogIHRpdGxlOiAnVGhlIEVsZW1lbnRzIG9mIFN0YXRpc3RpY2FsIExlYXJuaW5nOiBEYXRhIE1pbmluZywgSW5mZXJlbmNlLCBhbmQgUHJlZGljdGlvbicKICBhdXRob3I6IEhhc3RpZSwgVC4gYW5kIFRpYnNoaXJhbmksIFIuIGFuZCBGcmllZG1hbiwgSi5ILgogIHB1Ymxpc2hlcjogU3ByaW5nZXIKICB0eXBlOiBib29rCiAgaXNzdWVkOgogICAgeWVhcjogMjAwOQotIGlkOiBqYW1lczIwMTdpbnRyb2R1Y3Rpb24KICB0aXRsZTogIkFuIEludHJvZHVjdGlvbiBUbyBTdGF0aXN0aWNhbCBMZWFybmluZyIKICBhdXRob3I6IEphbWVzLCBHYXJldGgsIERhbmllbGEgV2l0dGVuLCBUcmV2b3IgSGFzdGllLCBhbmQgUm9iZXJ0IFRpYnNoaXJhbmkKICBwdWJsaXNoZXI6IFNwcmluZ2VyCiAgaXNzdWVkOgogICAgeWVhcjogMjAxNwotIGlkOiBlZnJvbjIwMTZjb21wdXRlcgogIHRpdGxlOiAiQ29tcHV0ZXIgQWdlIFN0YXRpc3RpY2FsIEluZmVyZW5jZSIKICBhdXRob3I6IEVmcm9uLCBCcmFkbGV5IGFuZCBIYXN0aWUsIFRyZXZvcgogIHB1Ymxpc2hlcjogQ2FtYnJpZGdlIFVuaXZlcnNpdHkgUHJlc3MKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDE2Ci0gaWQ6IG1vbG5hcjIwMTkKICB0aXRsZTogIkludGVycHJldGFibGUgTWFjaGluZSBMZWFybmluZyIKICBhdXRob3I6IENocmlzdG9waCBNb2xuYXIKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDE5CiAgVVJMOiDigJxodHRwczovL2NocmlzdG9waG0uZ2l0aHViLmlvL2ludGVycHJldGFibGUtbWwtYm9va+KAnQotIGlkOiBtdXJwaHkyMDEybWFjaGluZQogIHRpdGxlOiAiTWFjaGluZSBMZWFybmluZzogQSBQcm9iYWJpbGlzdGljIFBlcnNwZWN0aXZlIgogIGF1dGhvcjogTXVycGh5LCBLZXZpbiBQCiAgcHVibGlzaGVyOiBNSVQgUHJlc3MKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDEyCiAgVVJMOiAiaHR0cHM6Ly9jaHJpc3RvcGhtLmdpdGh1Yi5pby9pbnRlcnByZXRhYmxlLW1sLWJvb2siCi0gaWQ6IHByb2tob3JlbmtvdmEyMDE3Y2F0Ym9vc3QKICB0aXRsZTogIkNhdEJvb3N0OiBVbmJpYXNlZCBCb29zdGluZyBXaXRoIENhdGVnb3JpY2FsIEZlYXR1cmVzIgogIGF1dGhvcjogUHJva2hvcmVua292YSwgTGl1ZG1pbGEgYW5kIEd1c2V2LCBHbGViIGFuZCBWb3JvYmV2LCBBbGVrc2FuZHIgYW5kIERvcm9ndXNoLCBBbm5hIFZlcm9uaWthIGFuZCBHdWxpbiwgQW5kcmV5CiAgaXNzdWVkOgogICAgeWVhcjogMjAxNwogIFVSTDogImh0dHBzOi8vYXJ4aXYub3JnL3BkZi8xNzA2LjA5NTE2LnBkZiIKLSBpZDogY2hlbjIwMTZ4Z2Jvb3N0CiAgdGl0bGU6ICJYR0Jvb3N0OiBBIFNjYWxhYmxlIFRyZWUgQm9vc3RpbmcgU3lzdGVtIgogIGF1dGhvcjogQ2hlbiwgVGlhbnFpIGFuZCBHdWVzdHJpbiwgQ2FybG9zCiAgaXNzdWVkOgogICAgeWVhcjogMjAxNgogIFVSTDogImh0dHBzOi8vYXJ4aXYub3JnL3BkZi8xNjAzLjAyNzU0LnBkZiIKLS0tCgojIFNUMzEwIENvdXJzZSBQcm9qZWN0CgpUaGUgYWltIG9mIHRoaXMgcHJvamVjdCBpcyB0byBkZW1vbnN0cmF0ZSB0aGUgdXNlIG9mIG1hY2hpbmUgbGVhcm5pbmcgdGVjaG5pcXVlcyBsZWFybnQgaW4gdGhlIFNUMzEwIE1hY2hpbmUgTGVhcm5pbmcgbW9kdWxlLiBXZSByZWx5IG9uIGJvdGggbGluZWFyIChMb2dpc3RpYyBSZWdyZXNzaW9uKSBhbmQgbm9uLWxpbmVhciBtZXRob2RzIChSYW5kb20gRm9yZXN0cyBhbmQgR3JhZGllbnQgQm9vc3RlZCBEZWNpc2lvbiBUcmVlcykgZm9yIGEgY2xhc3NpZmljYXRpb24gcHJvYmxlbS4KCioqUmVtYXJrKio6IElmIGV4ZWN1dGluZyB0aGlzIG5vdGVib29rcyBhcyBhIGAuUm1kYCBmaWxlLCBlbnN1cmUgdGhhdCBhbGwgbGlicmFyaWVzIGFyZSBpbnN0YWxsZWQgYW5kIHRoYXQgdGhlIGNlbGxzIGFyZSBleGVjdXRlZCBpbiBzZXF1ZW50aWFsIG9yZGVyLgoKIyMgRGF0YXNldAoKV2UgaGF2ZSBvYnRhaW5lZCBkYXRhIGZyb20gdGhlIFtLYWdnbGUgTWFyY2ggVGFidWxhciBQbGF5Z3JvdW5kXSgjaHR0cHM6Ly93d3cua2FnZ2xlLmNvbS9jL3RhYnVsYXItcGxheWdyb3VuZC1zZXJpZXMtbWFyLTIwMjEvb3ZlcnZpZXcpIGNvbXBldGl0aW9uLiBUaGUgZGF0YSBjb25zaXN0cyBvZiAqYW5vbnltaXNlZCBmZWF0dXJlcyosIHdoaWNoIGNvcnJlc3BvbmQgdG8gYSBiaW5hcnkgb3V0Y29tZSB2YXJpYWJsZTsgaW4gb3RoZXIgd29yZHMgdGhlIHRhc2sgaXMgYSAqKmNsYXNzaWZpY2F0aW9uIHByb2JsZW0qKi4gQWx0aG91Z2ggdGhlIGRhdGEgaXMgYW5vbnltaXNlZCwgd2UgYXJlIHRvbGQgdGhhdCBpdCBpcyBiYXNlZCBvbiBhIHJlYWwgZGF0YXNldCB0aGF0IGRlYWxzIHdpdGggcHJlZGljdGluZyB0aGUgYW1vdW50IG9mIGFuIGluc3VyYW5jZSBjbGFpbS4KCldlIGNvbnNpZGVyIHRoZSAqKlJPQy1BVUMgbWV0cmljKiogKFJlY2VpdmluZyBPcGVyYXRvciBDaGFyYWN0ZXJpc3RpYyBBcmVhIFVuZGVyIHRoZSBDdXJ2ZSksIGFuZCAqKmFjY3VyYWN5KiogbWV0cmljLiBHaXZlbiB0aGUgcHJvYmxlbSBpcyBpbmRpcmVjdGx5IG9uZSByZWxhdGVkIHRvIGluc3VyYW5jZSwgdGhlIG1vZGVsbGluZyBvdXRjb21lIG9mIGludGVyZXN0IGlzIG5vdCBvbmx5ICB0byBvYnRhaW4gdGhlIGNvcnJlY3QgcHJlZGljdGlvbnMgKGFjY3VyYWN5KSAsIGJ1dCBhbHNvIGFjY3VyYXRlIHByb2JhYmlsaXRpZXMsIHdoaWNoIGlzIHdoYXQgdGhlIEFVQyBtZXRyaWMgbWVhc3VyZXMuVGhlIHRlc3QgYWNjdXJhY3kKCmBgYHtyIGxvYWQtbGlicywgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeSh0aWR5bW9kZWxzKQpsaWJyYXJ5KHhnYm9vc3QpCmxpYnJhcnkoY2F0Ym9vc3QpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGJyb29tKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkoYXJtKQpsaWJyYXJ5KGNhcikgI291dGxpZXIKbGlicmFyeSh0aWR5cikKbGlicmFyeShnbG1uZXQpCmxpYnJhcnkoY2FyZXQpCmxpYnJhcnkodGlkeW1vZGVscykKbGlicmFyeShwUk9DKQpsaWJyYXJ5KHJhbmRvbUZvcmVzdCkKbGlicmFyeShlMTA3MSkKbGlicmFyeShhcm0pCmxpYnJhcnkoZGF0YS50YWJsZSkKZGYgPC0gcmVhZC5jc3YoZmlsZSA9ICIuLi9kYXRhL3RyYWluLmNzdiIpCmNhdChjKCJUaGUgZGltZW5zaW9ucyBvZiB0aGUgYXJyYXkgYXJlIDoiLCBkaW0oZGYpWzFdLCAiLCAiLCBkaW0oZGYpWzJdKSkKYGBgClRoZSBkYXRhc2V0IGNvbnNpc3RzIG9mIDMwIGZlYXR1cmVzLCAgMTkgKmNhdGVnb3JpY2FsIHZhcmlhYmxlcyogYW5kIDExIG51bWVyaWNhbCB2YXJpYWJsZXMuLCBhbmQgYSBiaW5hcnkgb3V0Y29tZSB2YXJpYWJsZSBgdGFyZ2V0YC4gV2Ugd2lsbCBuZWVkIHRvIHByb2Nlc3MgdGhlc2UgY2F0ZWdvcmljYWwgdmFyaWFibGVzIGluIHNvbWUgbWFubmVyLCB3aGljaCB3ZSBzaGFsbCBjb25zaWRlciBpbiB0aGUgW3N1YnNlcXVlbnQgc2VjdGlvbl0oI3ByZXByb2Nlc3NpbmcpLgoKQSBjaGFsbGVuZ2UgaXMgdGhhdCB3ZSBoYXZlIG5vICpzcGVjaWZpYyogZG9tYWluIGtub3dsZWRnZSBhYm91dCB0aGUgbWVhbmluZyBvZiBwYXJ0aWN1bGFyIGZlYXR1cmVzLCBhbmQgd2hldGhlciB0aGV5IG1heSBiZSB1c2VmdWwuIE5vbmV0aGVsZXNzLCB3ZSBjYW4gcmVzb3J0IHRvIG1vZGVsIGludGVycHJldGFiaWxpdHkgbWV0aG9kcyBbQG1vbG5hcjIwMTldIC0gaW4gdGhlIGxpbmVhciBjYXNlLCB3ZSBjYW4gZXhhbWluZSBjb2VmZmljaWVudHMgYW5kIHRoZWlyIHN0YXRpc3RpY2FsIHNpZ25pZmljYW5jZSwgYW5kIGluIHRoZSBjYXNlIG9mIHRyZWUtYmFzZWQgbW9kZWxzLCB3ZSBjYW4gdXRpbGlzZSBmZWF0dXJlIGltcG9ydGFuY2VzLCBwYXJ0aWFsIGRlcGVuZGVuY2UgcGxvdHMsIGFuZCBzaGFwbGV5IHZhbHVlcy4KCiMjIFByZXByb2Nlc3NpbmcKCldlIGZpcnN0IHJlbW92ZSB0aGUgZmlyc3QgY29sdW1uIGBpZGAsIHdoaWNoIHJlcHJlc2VudHMgYW4gdW5pcXVlIGlkZW50aWZpZXIgZm9yIGVhY2ggb2JzZXJ2YXRpb24uIFdlIHRoZW4gY29udmVydCB0aGUgZmlyc3QgMTkgY29sdW1ucywgd2hpY2ggYXJlIGNhdGVnb3JpY2FsIHZhcmlhYmxlcyBpbnRvIHRoZSAqZmFjdG9yKiBkYXRhIHR5cGUgaW4gUiwgVG8gcmVkdWNlIGNvbXB1dGF0aW9uYWwgdGltZSwgd2Ugc3Vic2FtcGxlIDQwMDAgb2JzZXJ2YXRpb25zIGZyb20gdGhlIGNvbXBsZXRlIGRhdGFzZXQgb2YgMzAwLDAwMCBvYnNlcnZhdGlvbnMuIEZvciBvdXIgc3Vic2VxdWVudCBhbmFseXNpcywgd2Ugd2lsbCB1c2Ugb25seSB0aGlzIHN1YnNhbXBsZSBvZiA0MDAwIG9ic2VydmF0aW9ucywgYWx0aG91Z2ggdGhlIGFwcHJvYWNoZXMgY2FuIGJlIGV4dGVuZGVkIHRvIGEgbGFyZ2VyIGRhdGFzZXQgZ2l2ZW4gZ3JlYXRlciBjb21wdXRhdGlvbmFsIHJlc291cmNlcy4gIFdlIGZ1cnRoZXIgcGFydGl0aW9uIHRoZSA0MDAwIG9ic2VydmF0aW9ucywgaW50byBhIHRyYWluIHNldCBvZiAzMDAwIG9ic2VydmF0aW9ucyBhbmQgYSB0ZXN0IHNldCBvZiAgMTAwMCBvYnNlcnZhdGlvbnMuIEFsbCB0cmFpbmluZyBhbmQgdHVuaW5nIGFyZSBwZXJmb3JtZWQgb24gdGhlIHRyYWluaW5nIGRhdGEsIGFuZCB3ZSB3aWxsIGNvbnNpZGVyIG1vZGVsIHBlcmZvcm1hbmNlIG9uIHRoZSB0ZXN0IHNldCBwZXJmb3JtYW5jZSBzY29yZXMuIAoKYGBge3IgcGFydGl0aW9ufQpyb3duYW1lcyhkZikgPSBkZiRpZApkZiA9IGRmWywtMV0gIyByZW1vdmUgaWQgY29sdW1uCmNhdF9mZWF0cyA9IDE6MTkgIyB0aGUgZmlyc3QgMTkgY29sdW1ucyBhcmUgY2F0ZWdvcmljYWwgCmNvbnRfZmVhdHMgPC0gMjA6MzAgIyBhbmQgdGhlIG5leHQgMTEgYXJlIGNvbnRpbnVvdXMKZGZbLGNhdF9mZWF0c10gPC0gbGFwcGx5KGRmWyxjYXRfZmVhdHNdLCBhcy5mYWN0b3IpCmRmJHRhcmdldCA8LSBhcy5mYWN0b3IoZGYkdGFyZ2V0KQojIHN1YnNhbXBsZSB0aGUgZGF0YSBmb3IgZmFzdGVyIG1vZGVsIGltcHV0YXRpb24Kc2V0LnNlZWQoMSkKc2FtID0gc2FtcGxlKDE6bnJvdyhkZiksIDQwMDApCmRmX3NhbXBsZSA9IGRmW3NhbSxdCiMgUGFydGl0aW9uIGRhdGEgaW50byB0cmFpbiBhbmQgdGVzdDsgdGVzdCB3aWxsIGJlIG91ciBvb3MgZGF0YQpzZXQuc2VlZCgxKQpkZl9zcGxpdCA8LSBpbml0aWFsX3NwbGl0KGRmX3NhbXBsZSwgcHJvcCA9IDMvNCkKZGZfdHJhaW4gPC0gdHJhaW5pbmcoZGZfc3BsaXQpCmRmX3Rlc3QgPC0gdGVzdGluZyhkZl9zcGxpdCkKYGBgCgojIyBFeHBsb3JhdG9yeSBEYXRhIEFuYWx5c2lzCgojIyMjIFVuaXZhcmlhdGUgRURBCldlIG9ic2VydmUgdGhhdCB0aGUgdW5pdmFyaWF0ZSBkaXN0cmlidXRpb25zIG9mIHRoZSAqY29udGludW91cyogdmFyaWFibGVzIGFyZSBhbGwgbXVsdGktbW9kYWwgYW5kIG5vbi1ub3JtYWwsIGJ1dCB0aGV5IGFyZSBhbGwgbm9ybWFsaXNlZCB0byB0aGUgcmFuZ2Ugb2YgJFswLCAxXSQuCmBgYHtyIGNvbnQtdml6fQpkZiAlPiUgcGl2b3RfbG9uZ2VyKGNvbHMgPSBzdGFydHNfd2l0aCgiY29udCIpLCBuYW1lc190byAgPSAiY29udCIpICU+JSAKICAgZ2dwbG90KGFlcyh4ID0gdmFsdWUpKSsKICAgZ2VvbV9oaXN0b2dyYW0oYmlucyA9IDEwMCwgYWxwaGEgPSAwLjg1KSsKICAgZ2d0aXRsZSgiQ29udGludW91cyBmZWF0dXJlcyBkaXN0cmlidXRpb24iKSsKICAgZmFjZXRfd3JhcChjb250fi4sc2NhbGVzID0gImZyZWUiKSArCiAgIHRoZW1lX21pbmltYWwoKQpgYGAKRnJvbSB0aGUgZGlzdHJpYnV0aW9ucyBvZiBjYXRlZ29yaWNhbCB2YXJpYWJsZXMsIHdlIHNlZSB0aGF0IHRoZXJlIGFyZSB2YXJpYWJsZXMgd2l0aCBzdWJzdGFudGlhbGx5IG1vcmUgb2JzZXJ2YXRpb25zIGluIG9uZSBjYXRlZ29yeSwgYW5kIGFsc28gdmFyaWFibGVzIHdpdGggYSBoaWdoIG51bWJlciBvZiAoJD41MCQpIGNhdGVnb3JpZXMsIHdoaWNoIHdpbGwgYmUgYW4gaXNzdWUgdG8gYWRkcmVzcyBpbiBvdXIgcHJlcHJvY2Vzc2luZyBzdGVwLiAgCmBgYHtyIGNhdC12aXp9CmRmICU+JSBwaXZvdF9sb25nZXIoY29scyA9IGNvbnRhaW5zKGMoImNhdCIpKSwgbmFtZXNfdG8gID0gImNhdCIpICU+JSAKICAgZ2dwbG90KGFlcyh4ID0gdmFsdWUpKSsKICAgZ2VvbV9iYXIoYWxwaGEgPSAwLjg1KSsKICAgZ2d0aXRsZSgiQ2F0ZWdvcmljYWwgZmVhdHVyZXMgZGlzdHJpYnV0aW9uIikrCiAgIGZhY2V0X3dyYXAoY2F0fi4sc2NhbGVzID0gImZyZWUiKSsKICAgdGhlbWVfbWluaW1hbCgpCmBgYAoKCgojIyMgQml2YXJpYXRlIEVEQQoKV2UgZ3JvdXAgdGhlIGNvbnRpbnVvdXMgdmFyaWFibGVzIGJ5IHRoZSB0YXJnZXQgYW5kIHBsb3QgdGhlbSBhcyBib3hwbG90cyB0byBjaGVjayBmb3IgYW55IG9idmlvdXMgZGlmZmVyZW5jZXMgZGlzY2VybmlibGUgYnkgZXllLiBGcm9tIHRoZSBwbG90cywgY2xhaW1zIHdpdGggYHRhcmdldCA9PSAxYCBoYXZlIGxvd2VyIHZhbHVlcyBvZiBjb250MyBvbiBhdmVyYWdlIChtZWRpYW4pIHRoYW4gY2xhaW1zIHdpdGggYHRhcmdldCA9PSAwYCwgaGVuY2Ugd2Ugd291bGQgZXhwZWN0IGEgbmVnYXRpdmUgcmVsYXRpb25zaGlwIGJldHdlZW4gY29udDMgYW5kIHRhcmdldC4gQ2xhaW1zIHdpdGggdGFyZ2V0PTEgYWxzbyBoYXZlIGEgaGlnaGVyIG1lZGlhbiB2YWx1ZSBvZiBjb250NCB0aGFuIGNsYWltcyB3aXRoIGB0YXJnZXQgPT0gMGAuIEluIGFkZGl0aW9uLCB3ZSBzZWUgYSBncm91cCBvZiBvYnNlcnZhdGlvbnMgYXQgdGhlIHRhaWwgZW5kcyBmb3IgYGNvbnQwLCBjb250NSwgY29udDcsIGNvbnQ4LCBjb250OSwgY29udDEwYCwgd2hpY2ggbWF5IGJlIGluZGljYXRpdmUgb2Ygb3V0bGllcnMuIFRoaXMgd2lsbCBiZSBhZGRyZXNzZWQgaW4gYSBbc3Vic2VxdWVudCBzZWN0aW9uXSgjbG9naXN0aWMtcmVncmVzc2lvbikuCgpgYGB7ciBjb250LWJ5LXRhcmdldH0KY29udC5zdGFja2VkIDwtIGdhdGhlcihkYXRhPWRmWywgYyhjb250X2ZlYXRzLCAzMSldLC10YXJnZXQsa2V5PSJ2YXIiLHZhbHVlPSJ2YWx1ZSIpCnAuY29udCA8LSBnZ3Bsb3QoY29udC5zdGFja2VkLGFlcyh4PXRhcmdldCx5PXZhbHVlKSxmaWxsPWZhY3Rvcih2YWx1ZSkpICsgZ2VvbV9ib3hwbG90KCkgKyBjb29yZF9mbGlwKCkgKyBmYWNldF93cmFwKH52YXIsIHNjYWxlcz0iZnJlZV94IikKcC5jb250CmBgYApGb3IgY2F0ZWdvcmljYWwgdmFyaWFibGVzLCB3ZSB1c2Ugc3RhY2tlZCBiYXIgcGxvdHMgdG8gc2hvdyB0aGUgcGVyY2VudGFnZXMgb2Ygb2JzZXJ2YXRpb25zIGluIGVhY2ggY2F0ZWdvcnkgdGhhdCBjb3JyZXNwb25kIHRvIGB0YXJnZXQgPT0gMGAgYW5kIGB0YXJnZXQgPT0gMWAgcmVzcGVjdGl2ZWx5LiBBIG11Y2ggbGFyZ2VyIHByb3BvcnRpb24gb2YgY2xhaW1zIHdpdGggYGNhdDEzID09IEJgIGFwcGVhciB0byBiZSBhc3NvY2lhdGVkIHdpdGggYHRhcmdldCA9PSAxYCBjb21wYXJlZCB0byBgY2F0MTMgPT0gQWAuIE9uIHRoZSBvdGhlciBoYW5kLCBhIG11Y2ggbGFyZ2VyIHBlcmNlbnRhZ2Ugb2YgY2xhaW1zIGNvcnJlc3BvbmQgdG8gYHRhcmdldCA9PSAwYCBpZiBgY2F0MThgIGlzIGBBYCBvciBgQmAsIHRoYW4gaWYgYGNhdDE4YCBpcyBgQ2Agb3IgYERgLgoKYGBge3IgY2F0LWJ5LXRhcmdldCwgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KZzEgPC0gYygxOjEwLDMxKQpnMiA8LSBjKDExOjE5LDMxKQpjYXRlLnN0YWNrZWQxIDwtIGdhdGhlcihkYXRhPWRmWyxnMV0sLXRhcmdldCxrZXk9InZhciIsdmFsdWU9InZhbHVlIikKcC5jYXRlMSA8LSBnZ3Bsb3QoY2F0ZS5zdGFja2VkMSxhZXMoeD12YWx1ZSxmaWxsPXRhcmdldCkpICsgZ2VvbV9iYXIocG9zaXRpb249ImZpbGwiKSArIHNjYWxlX3lfY29udGludW91cyhuYW1lID0gIldpdGhpbiBncm91cCBQZXJjZW50YWdlIiwgbGFiZWxzID0gc2NhbGVzOjpwZXJjZW50KSArIGZhY2V0X3dyYXAofnZhciwgc2NhbGVzPSJmcmVlX3giKQpjYXRlLnN0YWNrZWQyIDwtIGdhdGhlcihkYXRhPWRmWyxnMl0sLXRhcmdldCxrZXk9InZhciIsdmFsdWU9InZhbHVlIikKcC5jYXRlMiA8LSBnZ3Bsb3QoY2F0ZS5zdGFja2VkMixhZXMoeD12YWx1ZSxmaWxsPXRhcmdldCkpICsgZ2VvbV9iYXIocG9zaXRpb249ImZpbGwiKSArIHNjYWxlX3lfY29udGludW91cyhuYW1lID0gIldpdGhpbiBncm91cCBQZXJjZW50YWdlIiwgbGFiZWxzID0gc2NhbGVzOjpwZXJjZW50KSArIGZhY2V0X3dyYXAofnZhciwgc2NhbGVzPSJmcmVlX3giKQpwLmNhdGUxCnAuY2F0ZTIKYGBgCgpXZSBhbHNvIGluc3BlY3QgdGhlIGNvcnJlbGF0aW9uIG1hdHJpeCBmb3Igb3VyICpjb250aW51b3VzKiB2YXJpYWJsZXMuIFRoZXJlIHNlZW1zIHRvIGJlIGEgY2x1c3RlciBvZiB2YXJpYWJsZXMgLSBgY29udDEsIGNvbnQyLCBjb250OGAgLSB0aGF0IGFyZSBoaWdobHkgY29ycmVsYXRlZCB3aXRoIGVhY2ggb3RoZXIuIFRoaXMgY291bGQgbGVhZCB0byBwcm9ibGVtcyB3aXRoIG11bHRpY29sbGluZWFyaXR5IHdoZW4gdXNpbmcgbGluZWFyIG1vZGVscy4KCmBgYHtyIGNvci1tYXR9CmRmX251bSA8LSBkZlssIGNvbnRfZmVhdHNdCmNvcl9tYXRyaXggPC0gY29yKGRmX251bSkKaGVhdG1hcChjb3JfbWF0cml4KQpgYGAKRmluYWxseSwgd2UgdXNlIFByaW5jaXBhbCBDb21wb25lbnRzIEFuYWx5c2lzIChQQ0EpIGFzIGEgbWVhbnMgdG8gdmlzdWFsaXNlIHRoZSBkYXRhIGluIGxvdy1kaW1lbnNpb24sIHRvIGRldGVybWluZSBpZiB0aGVyZSBhcmUgYW55IGV4cGxpY2l0bHkgZGlzY2VybmlibGUgdHJlbmRzLiBCeSBleWUsIHRoZSBjbGFzc2VzIGRvIG5vdCBhcHBlYXIgdG8gYmUgbGluZWFybHkgc2VwZXJhYmxlIC0gd2hpY2ggc3VnZ2VzdCBhIG5vbi1saW5lYXIgbWV0aG9kIG1heSBiZSBtb3JlIGVmZmVjdGl2ZS4gVGhlcmUgZG8gbm90IGFwcGVhciB0byBiZSBhbnkgc2lnbmlmaWNhbnQgZGlmZmVyZW5jZSBpbiB0aGUgUENBIHJlcHJlc2VudGF0aW9ucyBmb3IgZWFjaCBjbGFzcy4KCmBgYHtyIHBjYS12aXp9CnBjcyA8LSBwcmNvbXAoZGZbLGNvbnRfZmVhdHNdKQpzZXQuc2VlZCgyMDIxKQppbmQgPC0gc2FtcGxlKDE6ZGltKGRmKVsxXSwgMjAwMDApCnNhbXBsZSA8LSBkYXRhLmZyYW1lKHBjcyR4W2luZCwxXSwgcGNzJHhbaW5kLDJdLCBkZltpbmQsICJ0YXJnZXQiXSkKbmFtZXMoc2FtcGxlKSA9IGMoInBjMSIsICJwYzIiLCAieSIpCmdncGxvdChzYW1wbGUpICsgZ2VvbV9qaXR0ZXIoYWVzKHggPSBwYzEsIHkgPSBwYzIsIGNvbG91ciA9IGZhY3Rvcih5KSksYWxwaGE9MC43KSArIGdndGl0bGUoJ1ByaW5jaXBhbCBDb21wb25lbnRzJykKY3VtdWxfdmFyIDwtIGN1bXN1bShwY3Mkc2Rldl4yIC8gc3VtKHBjcyRzZGV2XjIpKQpnZ3Bsb3QoZGF0YS5mcmFtZShmZWF0dXJlID0gMToxMSwgY3VtdWxfdmFyID0gY3VtdWxfdmFyKSkgKyBnZW9tX2xpbmUoYWVzKHggPSBmZWF0dXJlLHkgPSBjdW11bF92YXIpKQpgYGAKU291cmNlOiBodHRwczovL3N0YXRzYW5kci5jb20vYmxvZy9vdXRsaWVycy1kZXRlY3Rpb24taW4tci8KCiMjIE1vZGVsbGluZwoKV2UgZmlyc3QgY29uc2lkZXIgYSBuYWl2ZSAnYmFzbGluZScsIGluIHdoaWNoIHdlIGxldCBhbGwgcHJlZGljdGVkIGxhYmVscyBlcXVhbCAwIG9yIDEgKHdoaWNoZXZlciBsZWFkcyB0byB0aGUgZ3JlYXRlciBhY2N1cmFjeTsgdGhlIGFjY3VyYWN5IHdvdWxkIGJlIHRoZSBncmVhdGVyIG9mIGVpdGhlciAkXGhhdHt5fSQgb3IgJDEgLSBcaGF0e3l9JCkuIEluIHRoaXMgY2FzZSwgdGhlIGdyZWF0ZXIgYWNjdXJhY3kgb2YgJDAuNzQ1JCB3b3VsZCBiZSBvYnRhaW5lZCBpZiB3ZSBwcmVkaWN0IGFsbCBsYWJlbHMgYXMgYDBgLCB3aGljaCBzdWdnZXN0cyB0aGUgYDFgIGNsYXNzIGlzIGxlc3MgZnJlcXVlbnRseSBvY2N1cnJpbmcgaS5lLiBpbWJhbGFuY2VkIGNsYXNzaWZpY2F0aW9uLiBUaGlzIGlsbHVzdHJhdGVzIHRoZSBpc3N1ZSB3aXRoIHRoZSBhY2N1cmFjeSBtZXRyaWM6IHdlIG11c3QgY29tcGFyZSBvdXIgbW9kZWwgYWNjdXJhY3kgd2l0aCB0aGUgKm5haXZlKiBhY2N1cmFjeSBhbmQgb3RoZXIgYXBwcm9wcmlhdGUgYmVuY2htYXJrcyB0byBwcmV2ZW50IGEgbWlzbGVhZGluZyByZXN1bHQsIGFzIG91ci4gT24gdGhlIG90aGVyIGhhbmQsIHByZWRpY3RpbmcgYWxsIDFzIG9yIDBzIHdvdWxkIHJlc3VsdCBpbiB0aGUgd29yc3QgcG9zc2libGUgUk9DLUFVQyBzY29yZSBvZiAkMC41JC4KCmBgYHtyfQojIHRyYWluLXRlc3QKWF90cmFpbiA9IGFzLm1hdHJpeChkZl90cmFpblssZ3JlcGwoImNvbnQiLCBjb2xuYW1lcyhkZl90cmFpbikpXSkKeV90cmFpbiA9IGFzLm51bWVyaWMoYXMubWF0cml4KGRmX3RyYWluJHRhcmdldCkpClhfdGVzdCA9IGFzLm1hdHJpeChkZl90ZXN0WyxncmVwbCgiY29udCIsIGNvbG5hbWVzKGRmX3RyYWluKSldKQp5X3Rlc3QgPSBhcy5udW1lcmljKGFzLm1hdHJpeChkZl90ZXN0JHRhcmdldCkpCnJlc3VsdHMgPSBkYXRhLmZyYW1lKHRyYWluX2FjYyA9IG1heCgxIC0gbWVhbih5X3RyYWluKSwgbWVhbih5X3RyYWluKSksCiAgICAgICAgICAgICAgICAgICAgIHRyYWluX2F1YyA9IDAuNSwKICAgICAgICAgICAgICAgICAgICAgdGVzdF9hY2MgPSBtYXgoMSAtIG1lYW4oeV90ZXN0KSwgbWVhbih5X3Rlc3QpKSwKICAgICAgICAgICAgICAgICAgICAgdGVzdF9hdWMgPSAwLjUsCiAgICAgICAgICAgICAgICAgICAgIHJvdy5uYW1lcz1jKCJuYWl2ZSIpCiAgICAgICAgICAgICAgICAgICAgICkKcmVzdWx0cwpgYGAKCiMjIyBMb2dpc3RpYyBSZWdyZXNzaW9uIChGZXcgUHJlZGljdG9ycykKCkFzIGEgYmFzZWxpbmUgbW9kZWwsIHdlIGJ1aWxkIGEgc2ltcGxlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gd2l0aCBhIGZldyBwcmVkaWN0b3JzLCB3aGljaCBhcmUgc2VsZWN0ZWQgZnJvbSBvdXIgZXhwbG9yYXRvcnkgZGF0YSBhbmFseXNpcyB0byBoYXZlIGRpc2Nlcm5pYmxlIGRpZmZlcmVuY2VzIGluIHRhcmdldC4gVGhlc2UgYXJlIGBjb250MywgY29udDQsIGNhdDEzLCBjYXQxOGAuIFdlIHVzZSB0aGUgYGdsbWAgcGFja2FnZSB0byBmaXQgYSBsb2dpc3RpYyByZWdyZXNzaW9uLgoKYGBge3J9CmdsbTEgPC0gZ2xtKHRhcmdldH5jb250Mytjb250NCtjYXQxMytjYXQxOCxkYXRhPWRmX3RyYWluLCBmYW1pbHk9Ymlub21pYWwobGluaz0ibG9naXQiKSxjb250cm9sID0gbGlzdChtYXhpdCA9IDEwMCkpCnN1bW1hcnkoZ2xtMSkKYGBgCgpBbGwgZm91ciBwcmVkaWN0b3JzIGFyZSBzaWduaWZpY2FudCBhdCA1JSBsZXZlbCwgd2l0aCB0aGUgbW9zdCBzaWduaWZpY2FudCBwcmVkaWN0b3JzIGJlaW5nLi4uIFRoZSBjb2VmZmljaWVudHMgb2YgdGhlIGR1bW15IHZhcmlhYmxlcyBpbmRpY2F0ZSB0aGUgYXZlcmFnZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGxvZyBvZGRzIG9mIHRoYXQgZmFjdG9yIGxldmVsIGdyb3VwIGNvbXBhcmVkIHRvIHRoZSBiYXNlbGluZSBsZXZlbCBncm91cC4gSW4gb3VyIHJlZ3Jlc3Npb24sIHRoZSBmaXJzdCBjYXRlZ29yeSAoQSkgb2YgZWFjaCBjYXRlZ29yaWNhbCB2YXJpYWJsZSBpcyB0YWtlbiBhcyB0aGUgYmFzZWxpbmUgZ3JvdXAuIEZvciBleGFtcGxlLCB0aGUgY29lZmZpY2llbnQgb2YgYGNhdDEzYmAgaW1wbGllcyB0aGUgZm9sbG93aW5nIGVxdWF0aW9uOiAKJCRcdGV4dHtsb2dpdH0gUChcdGV4dHt0YXJnZXR9PTF8XHRleHR7Y2F0MTNifSA9IDEpIOKAkyBcdGV4dHtsb2dpdH0gUChcdGV4dHt0YXJnZXR9PTB8XHRleHR7Y2F0MTNifSA9IDEpID0gMS44NjgxLiAkJApJbiB3b3JkcywgdGhpcyBtZWFucyB0aGF0IGNsYWltcyB3aXRoIGBjYXQxM2IgPSAxYCBoYXZlIDMzJSBoaWdoZXIgbG9nIG9kZHMgb2YgdGFyZ2V0PTEgdGhhbiBjbGFpbXMgd2l0aCBbY2F0QV0uIEhvd2V2ZXIsIHdlIGNhbiBvbmx5IGFzc2VydCB0aGF0IHRoZXJlIGlzIHNvbWUgIGFzc29jaWF0aW9uIC0gaW4gdGhpcyBjYXNlIGl0IGlzIHN0YXRpc3RpY2FsbHkgc2lnbmlmaWNhbnQgcmVsYXRpb25zaGlwIHdpdGggdGhlIHAtdmFsdWUgYmVpbmcgYDIuMzZlLTA4YCAtIGJldHdlZW4gdGhlIHByZXNlbmNlIG9mIHRoZSB2YXJpYWJsZSBgY2F0MTNiID0gMWAgYW5kIHRoZSB0YXJnZXQgYmVpbmcgMSwgYnV0IG5vdCB3aGV0aGVyIHRoZXJlIGlzIGEgY2F1c2F0aW9uOyBpbiBwYXJ0aWN1bGFyLCBnaXZlbiB0aGUgbGFjayBvZiBrbm93bGVkZ2Ugb2Ygd2hhdCB0aGUgdmFyaWFibGUgcmVwcmVzZW50cywgd2UgY2Fubm90IGZvcm0gYW55IG1lYW5pbmdmdWwgaHlwb3RoZXNpcy4KClRvIGludGVycHJldCB0aGUgY29lZmZpY2llbnRzIG9mIHRoZSBjb250aW51b3VzIHZhcmlhYmxlcywgcmlzayByYXRpb3MgbmVlZCB0byBiZSBjYWxjdWxhdGVkIHVzaW5nIHNwZWNpZmljIHBhaXJzIG9mIHZhbHVlcyBvZiB0aGUgcHJlZGljdG9ycy4gVGhlIG5vbi1saW5lYXJpdHkgb2YgdGhlIGxvZ2lzdGljIGZ1bmN0aW9uIG1lYW5zIHRoYXQgYSBjaGFuZ2Ugb2Ygb25lIHVuaXQgaW4gdGhlIHZhbHVlIG9mIGEgcHJlZGljdG9yIGlzIG5vdCB0aGUgc2FtZSBhY3Jvc3MgdGhlIHJhbmdlIG9mIHRoZSBwcmVkaWN0b3IuCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpwcmVkX3RyYWluIDwtIHByZWRpY3QoZ2xtMSwgZGZfdHJhaW4sIHR5cGU9InJlc3BvbnNlIikKcHJlZF90ZXN0IDwtIHByZWRpY3QoZ2xtMSwgZGZfdGVzdCwgdHlwZT0icmVzcG9uc2UiKQoKZGlhZ25vc2lzIDwtIGZ1bmN0aW9uKHRyYWluX3ByZWQsIHRlc3RfcHJlZCwgdHJhaW5fdHJ1ZSwgdGVzdF90cnVlKXsKICB0cmFpbl9jbGFzc2VzIDwtIGlmZWxzZSh0cmFpbl9wcmVkID4gMC41LCAxLDApCiAgdGVzdF9jbGFzc2VzIDwtIGlmZWxzZSh0ZXN0X3ByZWQgPiAwLjUsIDEsMCkKICBhY2MxIDwtIG1lYW4odHJhaW5fY2xhc3NlcyA9PSB0cmFpbl90cnVlKQogIGF1YzEgPC0gYXVjKHJvYyh0cmFpbl90cnVlLCB0cmFpbl9wcmVkKSkKICBhY2MyIDwtIG1lYW4odGVzdF9jbGFzc2VzID09IHRlc3RfdHJ1ZSkKICBhdWMyIDwtIGF1Yyhyb2ModGVzdF90cnVlLCB0ZXN0X3ByZWQpKQogIGRhdGEuZnJhbWUodHJhaW5fYWNjPWFjYzEsIHRyYWluX2F1Yz1hdWMxLCB0ZXN0X2FjYyA9IGFjYzIsIHRlc3RfYXVjPWF1YzIpCn0KCnJlc3VsdHNbImdsbS1zbWFsbCIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJnbG0tc21hbGwiLF0KYGBgCgojIyMgU0dECgpUbyBmdWxmaWxsIHRoZSBwcm9qZWN0IHJlcXVpcmVtZW50cywgd2UgZGVtb25zdHJhdGUgYSBgZnJvbSBzY3JhdGNoJyBTdG9jaGFzdGljIEdyYWRpZW50IERlc2NlbnQgcm91dGluZSAgZm9yIGxvZ2lzdGljIHJlZ3Jlc3Npb24uIFRoZSBkZXJpdmlhdGlvbiBmb2xsb3dzIFtAaGFzdGllMjAwOWVsZW1lbnRzLCBwcC4gMTIwLTEyNl0KClRoZSBsb2dpc3RpYyBsb3NzIHdpdGggYSBcKCBcbWF0aGNhbHtMfV57Mn1cKSBwZW5hbHR5IGlzIGdpdmVuIGJ5OgoKJCRsKFxib2xkc3ltYm9se1xiZXRhfSkgPSAtXHN1bV97aSA9IDF9XntOfSB5X3tpfSBsb2cocCh4X3tpfSA7IFxib2xkc3ltYm9se1xiZXRhfSkpICsgKDEgLSB5X3tpfSkgbG9nKDEgLSBwKHhfe2l9IDsgXGJvbGRzeW1ib2x7XGJldGF9KSkgPSBcc3VtX3tpID0gMX1ee059IFxsZWZ0IFsgeV97aX1sb2cgXGxlZnQgKFxmcmFje3AoeF97aX0gOyBcYm9sZHN5bWJvbHtcYmV0YX0pfXsxIC0gcCh4X3tpfSA7IFxib2xkc3ltYm9se1xiZXRhfSl9IFxyaWdodCkgKyBsb2coMSAtIHAoeF97aX0gOyBcYm9sZHN5bWJvbHtcYmV0YX0pKSBccmlnaHQgXSQkCgokJCBsKFxib2xkc3ltYm9se1xiZXRhfSk9IC1cc3VtX3tpID0gMX1ee059XGxlZnQgW3lfe2l9IFxib2xkc3ltYm9se1xiZXRhfV57VH0geF97aX0gLSBsb2coMSArIGV4cChcYm9sZHN5bWJvbHtcYmV0YX1ee1R9eF97aX0pKSBccmlnaHQgXSQkClRoZW4gd2l0aCB0aGUgaW5jbHVzaW9uIG9mIHRoZSByZXVsYXJpc2F0aW9uIHRlcm06CgokJCBsKFxib2xkc3ltYm9se1xiZXRhfSkgPSAtXHN1bV97aSA9IDF9XntOfSBcbGVmdCBbeV97aX0gXGJvbGRzeW1ib2x7XGJldGF9XntUfSB4X3tpfSAtIGxvZygxICsgZXhwKFxib2xkc3ltYm9se1xiZXRhfV57VH14X3tpfSkpIFxyaWdodCBdIC0gXGxhbWJkYSBcYm9sZHN5bWJvbHtcYmV0YX1ee1R9IFxib2xkc3ltYm9se1xiZXRhfSQkCgoKVGhlIGdyYWRpZW50IGlzIGdpdmVuIGJ5OgoKJCRcbmFibGEoXGJvbGRzeW1ib2x7XGJldGF9KSA9IC1cc3VtX3tpID0gMX1ee059IFxsZWZ0IFsgeV97aX0geF97aX0gLSBcZnJhY3t4X3tpfWV4cChcYm9sZHN5bWJvbHtcYmV0YX1ee1R9IHhfe2l9KX17MSArIGV4cChcYm9sZHN5bWJvbHtcYmV0YX1ee1R9IHhfe2l9KX0gXHJpZ2h0XSAtIFxsYW1iZGEgMlxib2xkc3ltYm9se1xiZXRhfSQkCgpXZSB1c2UgdGhlIEJhcnppbGFpLUJvcndlaW4gbWV0aG9kIFtAbXVycGh5MjAxMm1hY2hpbmUsIHBwLiA0NDQtNDQ1XSB0byBkZXRlcm1pbmUgdGhlIHN0ZXAgc2l6ZS4KCmBgYHtyIGdyYWRpZW50LWRlc2NlbnR9CiMgYmluYXJ5IGNyb3NzZW50cm9weSAvIGxvZy1sb3NzCmxvZ19sb3NzIDwtIGZ1bmN0aW9uKHgsIHksIGJldGFzLCBsYW1iZGEpewogIGxvZ2l0cyA8LSB4ICUqJSBiZXRhcwogIC0gKHQoeSkgJSolIGxvZ2l0cyAtIHN1bShsb2coMSArIGV4cChsb2dpdHMpKSkgKyBsYW1iZGEgKiB0KGJldGFzKSAlKiUgYmV0YXMpIC8gZGltKHgpWzFdCn0KCiMgbG9naXN0aWMgcmVncmVzc2lvbiBncmFkaWVudHMKZ3JhZGllbnRzIDwtIGZ1bmN0aW9uKHgsIHksIGJldGFzLCBsYW1iZGEpewogIGxvZ2l0cyA8LSB4ICUqJSBiZXRhcwogIC0gKHQoeCkgJSolICh5IC0gZXhwKGxvZ2l0cykvKDEgKyBleHAobG9naXRzKSkpKSAtIGxhbWJkYSAqMiAqIGJldGFzIC8gZGltKHgpWzFdCn0KCnAgPSBkaW0oWF90cmFpbilbMl0KCmxhbWJkYSA9IDAKbl9pdGVycyA8LSAxMDAKaW5pdF9zdGVwX3NpemUgPC0gMWUtNgoKc2V0LnNlZWQoMjAyMSkKYmV0YV9pbml0IDwtIG1hdHJpeChybm9ybShwKSxucm93PXApCmJldGFfcGF0aCA8LSBtYXRyaXgocmVwKDAsIG5faXRlcnMgKiBwKSwgbnJvdyA9IG5faXRlcnMsIG5jb2w9cCkKYmV0YV9wYXRoWzEsXSA9IGJldGFfaW5pdAoKbGFzdF9ncmFkIDwtIGdyYWQgPC0gZ3JhZGllbnRzKFhfdHJhaW4sIHlfdHJhaW4sIGJldGFfcGF0aFsxLF0sIGxhbWJkYSkKYmV0YV9wYXRoWzIsXSA9IGJldGFfaW5pdCAtIGluaXRfc3RlcF9zaXplICogZ3JhZApncmFkIDwtIGdyYWRpZW50cyhYX3RyYWluLCB5X3RyYWluLCBiZXRhX3BhdGhbMixdLCBsYW1iZGEpCgpsb3NzZXMgPC0gcmVwKDAsIG5faXRlcnMpCgpmb3IgKGkgaW4gMzpuX2l0ZXJzKXsKICAgIHN0ZXBfc2l6ZSA8LSBhcy5udW1lcmljKHQoYmV0YV9wYXRoW2kgLSAxLF0gLSBiZXRhX3BhdGhbaSAtIDIsXSkgJSolIChncmFkIC0gbGFzdF9ncmFkKSAvIAogICAgICAgICAgICAgICAgICAgICh0KGdyYWQgLSBsYXN0X2dyYWQpICUqJSAoZ3JhZCAtIGxhc3RfZ3JhZCkpKQogICAgYmV0YV9wYXRoW2ksXSA8LSBiZXRhX3BhdGhbaSAtIDEsXSAtIHN0ZXBfc2l6ZSAqIGdyYWQKICAgIGxhc3RfZ3JhZCA8LSBncmFkCiAgICBncmFkIDwtIGdyYWRpZW50cyhYX3RyYWluLCB5X3RyYWluLCBiZXRhX3BhdGhbaSwgXSwgbGFtYmRhKQogICAgbG9zc2VzW2ldIDwtIGxvZ19sb3NzKFhfdHJhaW4sIHlfdHJhaW4sIGJldGFfcGF0aFtpLF0sIGxhbWJkYSkKfQpnZ3Bsb3QoZGF0YS5mcmFtZShzdGVwID0gMzpuX2l0ZXJzLCBsb3NzPWxvc3Nlc1szOm5faXRlcnNdKSkgKyAKICBnZW9tX2xpbmUoYWVzKHggPSBzdGVwLCB5ID0gbG9zcykpICsKICBnZ3RpdGxlKCJCaW5hcnkgQ3Jvc3NlbnRyb3B5IHZzLiBJdGVyYXRpb25zIikKYGBgCgoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KcHJlZF90cmFpbiA8LSBhcy5udW1lcmljKDEgLyAoMSArIGV4cCgtWF90cmFpbiAlKiUgYmV0YV9wYXRoWzEwMCxdKSkpCnByZWRfdGVzdCA8LSBhcy5udW1lcmljKDEgLyAoMSArIGV4cCgtWF90ZXN0ICUqJSBiZXRhX3BhdGhbMTAwLF0pKSkKcmVzdWx0c1sic2dkIixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbInNnZCIsXQpgYGAKCiMjIyBMb2dpc3RpYyBSZWdyZXNzaW9uIChBbGwgUHJlZGljdG9ycykKCldlIG5vdyBydW4gYSBsb2dpc3RpYyByZWdyZXNzaW9uIHVzaW5nIGFsbCB2YXJpYWJsZXMsIHVzaW5nIHRoZSBgZ2xtYCBwYWNrYWdlLgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFLCBvdXRwdXQ9RkFMU0V9CmdsbTIgPC0gZ2xtKHRhcmdldH4uLCBkYXRhPWRmX3RyYWluLCBmYW1pbHk9Ymlub21pYWwobGluaz0ibG9naXQiKSwgCiAgICAgICAgICAgIGNvbnRyb2wgPSBsaXN0KG1heGl0ID0gMTAwKSkKIyBkaXNwbGF5KGdsbTIpCmBgYAoKYGBge3IgZ2xtLWZ1bGwtcmVzdWx0cywgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KcHJlZF90cmFpbiA8LSBwcmVkaWN0KGdsbTIsIGRmX3RyYWluLCB0eXBlPSJyZXNwb25zZSIpCmdsbTIkeGxldmVscyA9IGxhcHBseShkZlssY2F0X2ZlYXRzXSwgbGV2ZWxzKQpwcmVkX3Rlc3QgPC0gcHJlZGljdChnbG0yLCBkZl90ZXN0LCB0eXBlPSJyZXNwb25zZSIpCnJlc3VsdHNbImdsbS1mdWxsIixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbImdsbS1mdWxsIixdCmFub3ZhKGdsbTEsIGdsbTIsIHRlc3Q9IkNoaXNxIikKYGBgCiMjIyBPdXRsaWVyIERldGVjdGlvbgoKIEF0IHRoaXMgc3RhZ2UsIHdlIHNlZWsgdG8gcmVtb3ZlIG91dGxpZXJzIHNwb3R0ZWQgaW4gdGhlIGJpdmFyaWF0ZSBwbG90cyBpbiBvdXIgZXhwbG9yYXRvcnkgYW5hbHlzaXMgZm9yIGNvbnQwLCBjb250NSwgY29udDcsIGNvbnQ4LCBjb250OSBhbmQgY29udDEwLiBUbyBpbnZlc3RpZ2F0ZSB0aGlzLCB3ZSBpZGVudGlmaWVkIG9ic2VydmF0aW9ucyB0aGF0IGxpZSBhdCB0aGUgZXh0cmVtZSBwZXJjZW50aWxlcyBvZiB0aGVzZSB2YXJpYWJsZXMuIFVzaW5nIHRoZSBIYW1wZWwgZmlsdGVyLCB3aGljaCBjb25zaWRlcnMgcG9pbnRzIGx5aW5nIG91dHNpZGUgdGhlIG1lZGlhbiBwbHVzIG9yIG1pbnVzIDMgbWVhbiBhYnNvbHV0ZSBkZXZpYXRpb25zIGFzIG91dGxpZXJzLCBtb3JlIHRoYW4gMjAwIG9ic2VydmF0aW9ucyBwZXIgdmFyaWFibGUgd2VyZSBjbGFzc2lmaWVkIGFzIHN1Y2guIFRoaXMgc3VnZ2VzdHMgdGhhdCB0aGVzZSBtYXkgbm90IGJlIG91dGxpZXJzIGJ1dCB0aGF0IHRoZSBkaXN0cmlidXRpb24gaXMganVzdCBoZWF2eS10YWlsZWQuIFdpdGhvdXQgZnVydGhlciBpbmZvcm1hdGlvbiBvbiB0aGUgcmVhc29uYWJsZSBzY2FsZSBvZiB2YWx1ZXMgdGhhdCBpbmRpdmlkdWFsIHZhcmlhYmxlcyBjYW4gdGFrZSAoYWxvbmcgd2l0aCB0aGUgZmFjdCB0aGF0IHRoZXkgYXJlIGFsbCBub3JtYWxpc2VkKSwgd2UgZmluZCBpdCBjaGFsbGVuZ2luZyB0byBjbGVhcmx5IGlkZW50aWZ5IG91dGxpZXJzIHRocm91Z2ggZGVzY3JpcHRpdmUgc3RhdGlzdGljcyBhbmQgZGVjaWRlIG5vdCB0byBleGNsdWRlIGFueSBzdWNoIHBvaW50cyB1c2luZyB0aGlzIGFwcHJvYWNoLiBXZSB3aWxsIHByb2NlZWQgdG8gZGV0ZWN0IGZvciBvdXRsaWVycyBpbiBhbm90aGVyIGFwcHJvYWNoIGxhdGVyIG9uLiAKCmBgYHtyfQpoYW1wZWxfZmlsdGVyIDwtIGZ1bmN0aW9uKGRmKXsKICAgbG93ZXJfYm91bmQgPC0gbWVkaWFuKGRmKSAtIDMgKiBtYWQoZGYsIGNvbnN0YW50ID0gMSkKICAgdXBwZXJfYm91bmQgPC0gbWVkaWFuKGRmKSArIDMgKiBtYWQoZGYsIGNvbnN0YW50ID0gMSkKICAgb3V0bGllcl9pbmQgPC0gd2hpY2goZGYgPCBsb3dlcl9ib3VuZCB8IGRmID4gdXBwZXJfYm91bmQpCiAgIHJldHVybihvdXRsaWVyX2luZCkKfQpwZXJjZW50aWxlX2ZpbHRlciA8LSBmdW5jdGlvbihkZiwgbHEgPSAwLjAwMSwgdXEgPSAwLjk5OSl7CiAgIGxvd2VyX2JvdW5kIDwtIHF1YW50aWxlKGRmLCBscSkKICAgdXBwZXJfYm91bmQgPC0gcXVhbnRpbGUoZGYsIHVxKQogICBvdXRsaWVyX2luZCA8LSB3aGljaChkZiA8IGxvd2VyX2JvdW5kIHwgZGYgPiB1cHBlcl9ib3VuZCkKICAgcmV0dXJuKG91dGxpZXJfaW5kKQp9CmhhbXBlbF9jb3VudCA8LSBmdW5jdGlvbih4KXtsZW5ndGgoaGFtcGVsX2ZpbHRlcih4KSl9CnBjdF9jb3VudCA8LSBmdW5jdGlvbih4KXtsZW5ndGgocGVyY2VudGlsZV9maWx0ZXIoeCkpfQoKb3V0bGllcl9jb3VudHMgPC0gZGF0YS5mcmFtZShsYXBwbHkoZGZfdHJhaW5bLCBjb250X2ZlYXRzXSwgaGFtcGVsX2NvdW50KSkKb3V0bGllcl9jb3VudHNbMiwgXSA8LSBkYXRhLmZyYW1lKGxhcHBseShkZl90cmFpblssIGNvbnRfZmVhdHNdLCBwY3RfY291bnQpKQpvdXRsaWVyX2NvdW50cwpgYGAKCgpXZSBhdHRlbXB0IHRvIGRldGVjdCBvdXRsaWVycyB1bmRlciBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24uIEZvcm1hbGx5LCBvdXRsaWVycyBhcmUgZGVmaW5lZCBhcyBvYnNlcnZhdGlvbnMgd2l0aCBhIHJlc3BvbnNlIHZlY3RvciB0aGF0IGlzIHVudXN1YWwgY29uZGl0aW9uYWwgb24gY292YXJpYXRlcy4gVGhleSBhcmUgZm9ybWFsbHkgaWRlbnRpZmllZCB0aHJvdWdoIHN0dWRlbnRpemVkIHJlc2lkdWFscy4gSW50dWl0aXZlbHksIG91dGxpZXJzIGhhdmUgbGFyZ2UgcmVzaWR1YWxzIGFuZCB3ZSBjYW4gZm9ybWFsbHkgdGVzdCAoYnkgbG9va2luZyBhdCB0aGUgQm9uZmVycm9uaS0tYWRqdXN0ZWQgcC12YWx1ZXMpIGlmIHRoZXNlIHJlc2lkdWFscyBhcmUgc2lnbmlmaWNhbnRseSBsYXJnZXIgdGhhbiB0aGUgb3RoZXIgb2JzZXJ2YXRpb25zLiBXZSB1c2UgdGhlIGBvdXRsaWVyVGVzdGAgZnVuY3Rpb24gZnJvbSB0aGUgYGNhcmAgdG8gZGV0ZXJtaW5lIHRoZSBvdXRsaWVycyBmcm9tIHRoZSBgZ2xtYCBtb2RlbC4KCk9ic2VydmF0aW9ucyB0aGF0IGFyZSBmYXIgZnJvbSB0aGUgYXZlcmFnZSBjb3ZhcmlhdGUgcGF0dGVybiBhcmUgY29uc2lkZXJlZCB0byBoYXZlIGhpZ2ggbGV2ZXJhZ2UgYW5kIGNhbiBiZSBtZWFzdXJlZCB1c2luZyB0aGUgaGF0IHZhbHVlLiBIZXJlLCB0aGVyZSBhcmUgbWFueSBwb2ludHMgd2l0aCBoaWdoIGxldmVyYWdlLiAKCmBgYHtyfQpvdXRsaWVyVGVzdChnbG0yKQpvdXRsaWVycyA8LSBhcy5udW1lcmljKG5hbWVzKG91dGxpZXJUZXN0KGdsbTIpJHApKQpgYGAKCkZpbmFsbHksIHdlIG1lYXN1cmUgZm9yIGluZmx1ZW5jZSwgd2hpY2ggaXMgYW4gb2JzZXJ2YXRpb24gdGhhdCBpcyBhbiBvdXRsaWVyIGFuZCBoYXZlIGhpZ2ggbGV2ZXJhZ2UuIFRoZXNlIGFyZSBsaWtlbHkgdG8gaW5mbHVlbmNlIHRoZSByZWdyZXNzaW9uIGNvZWZmaWNpZW50cyBhbmQgaW5mbHVlbmNlIGNhbiBiZSB0aG91Z2h0IG9mIGFzIHRoZSBwcm9kdWN0IG9mIGxldmVyYWdlIGFuZCBvdXRsaWVyLiBIZXJlLCB3ZSBwbG90IHN0dWRlbnRpc2VkIHJlc2lkdWFscyBhZ2FpbnN0IGhhdC12YWx1ZXMgd2l0aCB0aGUgc2l6ZSBvZiBhIGNpcmNsZSBiZWluZyBwcm9wb3J0aW9uYWwgdG8gdGhlIENvb2sncyBkaXN0YW5jZSBvZiBhbiBvYnNlcnZhdGlvbi0gYSBtZWFzdXJlIG9mIGluZmx1ZW5jZS4KCgpgYGB7cn0KaW5mbHVlbmNlSW5kZXhQbG90KGdsbTIsIHZhcnMgPSAiaGF0IikKYGBgCgpgYGB7cn0KaW5mbHVlbmNlUGxvdChnbG0yKQpgYGAKSGVyZSwgd2Ugb2JzZXJ2ZSB0aGF0IHRoZXJlIGFyZSBhIG51bWJlciBvZiBvYnNlcnZhdGlvbnMgd2l0aCBoaWdoIGluZmx1ZW5jZSAtIG91dGxpZXJzIHdpdGggaGlnaCBsZXZlcmFnZS4gVGh1cywgd2UgcmVtb3ZlIHRoZXNlIG9ic2VydmF0aW9ucyBhbmQgY29tcGFyZSB0aGUgcGVyZm9ybWFuY2Ugb2Ygb3VyIHVwZGF0ZWQgbW9kZWwgd2l0aCB0aGUgb3JpZ2luYWwgbW9kZWwuIAoKSW4gdGhlIGxhdGVyIG1vZGVscywgd2Ugd2lsbCBhbHNvIGV4Y2x1ZGUgdGhlIHNhbWUgb3V0bGllcnMuIAoKYGBge3IgaW5mbHVlbmNlcnN9CmluZmx1ZW5jZXJzIDwtIGFzLm51bWVyaWMocm93bmFtZXMoaW5mbHVlbmNlUGxvdChnbG0yKSkpCmdsbTJfaW5mbHVlbmNlcnMgPC0gdXBkYXRlKGdsbTIsIHN1YnNldCA9IGMoLWluZmx1ZW5jZXJzKSkKZ2xtMl9vdXRsaWVycyA8LSB1cGRhdGUoZ2xtMiwgc3Vic2V0ID0gYygtb3V0bGllcnMpKQpyZW1vdmFsX2xpc3QgPC0gdW5pb24ob3V0bGllcnMsIGluZmx1ZW5jZXJzKQpnbG0yX3JlbW92ZWQgPC0gdXBkYXRlKGdsbTIsIHN1YnNldCA9IGMoLXJlbW92YWxfbGlzdCkpCmNvbXBhcmVDb2VmcyhnbG0yLCBnbG0yX2luZmx1ZW5jZXJzLCBnbG0yX291dGxpZXJzLCBnbG0yX3JlbW92ZWQpCiMgYWN0dWFsbHkganVzdCB1c2UgZ2xtMiBhbmQgZ2xtMl9yZW1vdmVkCmBgYAoKCgojIyMgTG9naXN0aWMgKyBSaWRnZQoKR2l2ZW4gdGhlIGlzc3VlIG9mICpoaWdoIGRpbWVuc2lvbmFsaXR5Kiwgd2UgY29uc2lkZXIgYSByZWd1bGFyaXNlZCBmb3JtIG9mIGxvZ2lzdGljIHJlZ3Jlc3Npb24uIFdlIHVzZSB0aGUgYGdsbW5ldGAgcGFja2FnZTsgaW4gZG9pbmcgc28gd2UgbmVlZCB0byBjb252ZXJ0IHRoZSBkYXRhIHR5cGUgaW50byBtYXRyaWNlcy5UaGUgYGdsbW5ldGAgcGFja2FnZSByZXF1aXJlcyB0aGUgZGF0YSB0byBiZSBpbiBhICptYXRyaXgqIGRhdGEgdHlwZSwgYW5kIGhlbmNlIHdlIG1ha2UgdGhlIGNvcnJlc3BvbmRpbmcgYWRqdXN0bWVudC4KCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIG91dHB1dD1GQUxTRX0KWF90cmFpbiA9IGRmX3RyYWluWywgLWxlbmd0aChkZl90cmFpbildCnlfdHJhaW4gPC0gZGZfdHJhaW4kdGFyZ2V0ClhfdGVzdCA9IGRmX3Rlc3RbLCAtbGVuZ3RoKGRmX3Rlc3QpXQp5X3Rlc3QgPC0gZGZfdGVzdCR0YXJnZXQKWF90cmFpbiA9IG1vZGVsLm1hdHJpeCh+LiwgWF90cmFpbikKWF90ZXN0ID0gbW9kZWwubWF0cml4KH4uLCBYX3Rlc3QpCgpnbG0zIDwtIGN2LmdsbW5ldChYX3RyYWluLCB5X3RyYWluLCAKICAgICAgICAgICAgICAgICAgZmFtaWx5PSJiaW5vbWlhbCIobGluaz0ibG9naXQiKSwgYWxwaGE9MCkKZ2xtMwpgYGAKCgpgYGB7ciBnbG0tcmlkZ2Utc2NvcmVzLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpwcmVkX3RyYWluIDwtIGFzLm51bWVyaWMocHJlZGljdChnbG0zLCBYX3RyYWluLCB0eXBlPSJyZXNwb25zZSIpKQpwcmVkX3Rlc3QgPC0gYXMubnVtZXJpYyhwcmVkaWN0KGdsbTMsIFhfdGVzdCwgdHlwZT0icmVzcG9uc2UiKSkKcmVzdWx0c1siZ2xtLXJpZGdlIixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbImdsbS1yaWRnZSIsXQpgYGAKCiMjIyBOb25saW5lYXIgRml0IChUcmVlLWJhc2VkKQoKIyMjIyBSYW5kb20gRm9yZXN0CgpUbyBpbXByb3ZlIHBlcmZvcm1hbmNlLCB3ZSBkcmF3IG9uIHRoZSB1c2FnZSBvZiBub24tbGluZWFyIHRyZWUtYmFzZWQgbW9kZWxzLCBzcGVjaWZpY2FsbHkgcmFuZG9tIGZvcmVzdHMuIEludHVpdGl2ZWx5LCBhIHJhbmRvbSBmb3Jlc3QgYXZlcmFnZXMgZGlmZmVyZW50IGRlY2lzaW9uIHRyZWVzIChrbm93biBhcyBiYWdnaW5nKSBzbyBhcyB0byByZWR1Y2UgdGhlIHZhcmlhbmNlIG9mIGluZGl2aWR1YWwgdHJlZXMuCgpgYGB7cn0KY29udHJvbCA8LSB0cmFpbkNvbnRyb2wobWV0aG9kID0gImN2IiwKICAgIG51bWJlciA9IDIsCiAgICBzZWFyY2ggPSAiZ3JpZCIpCgpwdG09cHJvYy50aW1lKCkKc2V0LnNlZWQoMSkKcmYxIDwtIHRyYWluKHRhcmdldH4uLAogICAgZGF0YSA9IGRmX3RyYWluLAogICAgbWV0aG9kID0gInJmIiwKICAgIG1ldHJpYyA9ICJBY2N1cmFjeSIsCiAgICB0ckNvbnRyb2w9Y29udHJvbCwgCiAgICBpbXBvcnRhbmNlPVQsCiAgICBtYXhub2Rlcz0xMjgsCiAgICBudHJlZT02NCkKdGltZTE9cHJvYy50aW1lKCktcHRtCnRpbWUxCiNscyhyZjEpCnZhckltcFBsb3QocmYxJGZpbmFsTW9kZWwsIG4udmFyPTMwLCB0eXBlPTEpCmBgYApgYGB7ciByZi1zY29yZXMsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CnByZWRfdHJhaW4gPC0gcHJlZGljdChyZjEsZGZfdHJhaW4sdHlwZT0ncHJvYicpWywyXQpwcmVkX3Rlc3QgPC0gcHJlZGljdChyZjEsIGRmX3Rlc3QsIHR5cGU9J3Byb2InKVssMl0KcmVzdWx0c1sicmYiLF0gPC0gZGlhZ25vc2lzKHByZWRfdHJhaW4sIHByZWRfdGVzdCwgZGZfdHJhaW4kdGFyZ2V0LCBkZl90ZXN0JHRhcmdldCkKcmVzdWx0c1sicmYiLCBdCmBgYAoKVGhlIHJhbmRvbSBmb3Jlc3QgaGFzIGEgdGVzdCBhY2N1cmFjeSBvZiAwLjgzNiBhbmQgYSB0ZXN0IEFVQyBvZiAwLjg3Miwgd2hpY2ggaXMgaGlnaGVyIHRoYW4gdGhlIHByZXZpb3VzIGxpbmVhciBtb2RlbHMuIEhvd2V2ZXIsIHRoZSB0cmFpbiBhY2N1cmFjeSBhbmQgQVVDIGFyZSBzaWduaWZpY2FudGx5IGhpZ2hlciB0aGFuIHRoZSB0ZXN0IHBlcmZvcm1hbmNlLCB3aGljaCBzdWdnZXN0IHRoYXQgdGhlcmUgbWF5IGJlIHNvbWUgZGVncmVlIG9mIG92ZXJmaXR0aW5nIHRvIHRoZSB0cmFpbiBkYXRhLiAKClJhbmRvbSBmb3Jlc3RzIGNhbiBiZSB1c2VkIHRvIHJhbmsgdGhlIGltcG9ydGFuY2Ugb2YgZGlmZmVyZW50IGZlYXR1cmVzLiBTcGVjaWZpY2FsbHksIHRoZSB4LWF4aXMgaXMgdGhlIE1lYW4gRGVjcmVhc2UgQWNjdXJhY3ksIHdoaWNoIHJlcG9ydHMgaG93IG11Y2ggYWNjdXJhY3kgdGhlIG1vZGVsIGxvc2VzIHdoZW4gd2UgZXhjbHVkZSB0aGlzIHZhcmlhYmxlLiBUaGUgbW9yZSB0aGUgYWNjdXJhY3kgZmFsbHMgYnksIHRoZSBtb3JlIGltcG9ydGFudCB0aGUgcGFydGljdWxhciB2YXJpYWJsZSBpcy4gTm90ZSBoZXJlIHRoYXQgZm9yIGNhdGVnb3JpY2FsIHZhcmlhYmxlcywgZWFjaCBsZXZlbCBvZiB0aGUgY2F0ZWdvcnkgaXMgY2xhc3NpZmllZCBhcyBhIHNpbmdsZSB2YXJpYWJsZS4gSW4gdGhpcyBwbG90LCB3ZSByZWNvcmRlZCB0aGUgMzAgbW9zdCBpbXBvcnRhbnQgdmFyaWFibGVzLiAKCldlIHRoZW4gcnVuIGFub3RoZXIgcmFuZG9tIGZvcmVzdCB3aXRoIHRoZSBtb3N0IGltcG9ydGFudCBmZWF0dXJlcy4gSW4gZG9pbmcgc28sIHdlIGhvcGUgdG8gcmVkdWNlIHRoZSBkZWdyZWUgb2Ygb3ZlcmZpdHRpbmcgYnkgcmVkdWNpbmcgdGhlIGNvbXBsZXhpdHkgb2YgdGhlIG1vZGVsLiBIb3dldmVyLCBpdCBkb2VzIG5vdCBtYWtlIHNlbnNlIHRvIGRyb3Agc29tZSBsZXZlbHMgb2YgYSBjYXRlZ29yaWNhbCB2YXJpYWJsZSB3aGlsZSBpbmNsdWRpbmcgdGhlIG90aGVyIGxldmVscy4gSGVuY2UsIGFzIGxvbmcgYXMgYSBsZXZlbCBpcyBwcmVzZW50IGluIHRoZSB0b3AgMzAgZmVhdHVyZXMsIHdlIHdpbGwgaW5jbHVkZSB0aGUgZW50aXJlIGNhdGVnb3J5IGluIG91ciB1cGRhdGVkIHJhbmRvbSBmb3Jlc3QgbW9kZWwuIFRoaXMgcmVzdWx0cyBpbiB1cyBrZWVwaW5nIG9ubHkgMjIgdmFyaWFibGVzLCBmcm9tIGFuIGluaXRpYWwgMzAuIAoKT3VyIHJlZHVjZWQgcmFuZG9tIGZvcmVzdCBoYXMgYSBzbGlnaHRseSBpbXByb3ZlZCB0ZXN0IGFjY3VyYWN5IGFuZCBhIHNsaWdodGx5IGRlY3JlYXNlZCB0ZXN0IEFVQy4gSG93ZXZlciwgaXQgZG9lcyBub3Qgc29sdmUgdGhlIHBvdGVudGlhbCBwcm9ibGVtIG9mIG92ZXJmaXR0aW5nIGFzIHRyYWluIHBlcmZvcm1hbmNlIGlzIHN0aWxsIHNpZ25pZmljYW50bHkgYmV0dGVyIHRoYW4gdGVzdCBwZXJmb3JtYW5jZS4gSW4gZmFjdCwgdHJhaW4gcGVyZm9ybWFuY2Ugb24gdGhlIHJlZHVjZWQgcmFuZG9tIGZvcmVzdCBpcyBiZXR0ZXIgdGhhbiB0aGUgcmFuZG9tIGZvcmVzdCB3aXRoIGEgZnVsbCBzZXQgb2YgdmFyaWFibGVzIC0gdGhlIHJlZHVjZWQgY29tcGxleGl0eSBvZiB0aGUgbW9kZWwgZW5hYmxlZCBpdCB0byBoYXZlIGEgbG93ZXIgYmlhcyBvbiB0aGUgdHJhaW5pbmcgc2V0LiAKCiMjIyMgWEdCb29zdAoKRm9yIGNvbXBsZXRlbmVzcywgd2UgYWxzbyBjb25zaWRlciB0aGUgYHhnYm9vc3RgIGxpYnJhcnkgZm9yICoqZ3JhZGllbnQgYm9vc3RlZCBkZWNpc2lvbiB0cmVlcyoqLiBHcmFkaWVudCBCb29zdGVkIERlY2lzaW9uIFRyZWVzLiBUaGUgWEdCb29zdCBwYWNrYWdlLCBpbnRyb2R1Y2VkIGluIFtAY2hlbjIwMTZ4Z2Jvb3N0XSBpcyBhIHZhcmlhbnQgb2YgR3JhZGllbnQgQm9vc3RlZCBEZWNpc2lvbiBUcmVlcyBbQGhhc3RpZTIwMDllbGVtZW50cywgcHAuIDM1My0zNzRdCgoKYGBge3IgeGdiLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpkbXlfdHJhaW4gPC0gZHVtbXlWYXJzKCJ+LiIsIGRhdGEgPSBkZl90cmFpblssLWxlbmd0aChkZl90cmFpbildKQpkbXlfdGVzdCA8LSBkdW1teVZhcnMoIn4uIiwgZGF0YSA9IGRmX3Rlc3RbLC1sZW5ndGgoZGZfdGVzdCldKQpYX3RyYWluIDwtIGFzLm1hdHJpeChkYXRhLmZyYW1lKHByZWRpY3QoZG15X3RyYWluLGRmX3RyYWluKSkpClhfdGVzdCA8LSBhcy5tYXRyaXgoZGF0YS5mcmFtZShwcmVkaWN0KGRteV90ZXN0LGRmX3Rlc3QpKSkKeV90cmFpbiA9IGFzLmludGVnZXIoYXMubWF0cml4KGRmX3RyYWluJHRhcmdldCkpCnlfdGVzdCA9IGFzLmludGVnZXIoYXMubWF0cml4KGRmX3Rlc3QkdGFyZ2V0KSkKYnN0IDwtIHhnYm9vc3QoZGF0YSA9IFhfdHJhaW4sIGxhYmVsPXlfdHJhaW4sIG1heF9kZXB0aCA9IDIsIG5yb3VuZCA9IDEwLCAKICAgICAgICAgICAgICAgdmVyYm9zZT0wLAogICAgICAgICAgICAgICBvYmplY3RpdmU9J2JpbmFyeTpsb2dpc3RpYycsCiAgICAgICAgICAgICAgIGV2YWxfbWV0cmljPSJsb2dsb3NzIikKCnByZWRfdHJhaW4gPC0gcHJlZGljdChic3QsIFhfdHJhaW4sIHR5cGU9InJlc3BvbnNlIikKcHJlZF90ZXN0IDwtIHByZWRpY3QoYnN0LCBYX3Rlc3QsIHR5cGU9InJlc3BvbnNlIikKcmVzdWx0c1sieGdiIixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbInhnYiIsXQoKaW1wb3J0YW5jZV9tYXRyaXggPC0geGdiLmltcG9ydGFuY2UobW9kZWw9YnN0KQp4Z2IucGxvdC5pbXBvcnRhbmNlKGltcG9ydGFuY2VfbWF0cml4KQojIHNoYXBsZXkgdmFsdWVzCnhnYm9vc3Q6OnhnYi5nZ3Bsb3Quc2hhcC5zdW1tYXJ5KFhfdGVzdCwgbW9kZWwgPSBic3QsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0YXJnZXRfY2xhc3MgPSAxLCB0b3BfbiA9IDIwKSAgIyBTdW1tYXJ5IHBsb3QKYGBgCgojIyMjIENhdEJvb3N0CgpXZSBhbHNvIGNvbnNpZGVyIGJyaWVmbHkgZXhhbWluZSB0aGUgYGNhdGJvb3N0YCBsaWJyYXJ5IGZvciAqKmdyYWRpZW50IGJvb3N0ZWQgZGVjaXNpb24gdHJlZXMqKiwgZ2l2ZW4gaXRzIHBvcHVsYXJpdHkgb24gbWFjaGluZSBsZWFybmluZyBjb21wZXRpdGlvbnMgc3VjaCBhcyBLYWdnbGUuIFRoZSBDYXRCb29zdCBsaWJyYXJ5IGhhcyB0aGUgYWR2YW50YWdlIG9mIGxlYXJuaW5nIGEgdGFyZ2V0IGVuY29kaW5nIGZvciBjYXRlZ29yaWNhbCB2YXJpYWJsZXMuIEZyb20gYW4gaW1wbGVtZW50YXRpb24gcG9pbnQgb2YgdmlldywgdGhpcyBtYXkgcmVkdWNlIHRoZSBwcmVwcm9jZXNzaW5nIHRoYXQgbWF5IGJlIHJlcXVpcmVkLkZvciBkZXRhaWxzIG9uIENhdEJvb3N0LCByZWZlciB0byBbQHByb2tob3JlbmtvdmEyMDE3Y2F0Ym9vc3RdCgpgYGB7ciBjYiwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KWF90cmFpbiA9IGRmX3RyYWluWyxjKGNhdF9mZWF0cywgY29udF9mZWF0cyldCnlfdHJhaW4gPSBhcy5pbnRlZ2VyKGRmX3RyYWluJHRhcmdldCkKWF90ZXN0ID0gZGZfdGVzdFssYyhjYXRfZmVhdHMsIGNvbnRfZmVhdHMpXQp5X3Rlc3QgPSBhcy5pbnRlZ2VyKGRmX3Rlc3QkdGFyZ2V0KQoKcG9vbCA8LSBjYXRib29zdC5sb2FkX3Bvb2woWF90cmFpbiwgeV90cmFpbiwgY2F0X2ZlYXR1cmVzID0gY2F0X2ZlYXRzKQptb2RlbCA8LSBjYXRib29zdC50cmFpbihwb29sLCBwYXJhbXM9bGlzdChkZXB0aCA9IDgsIGl0ZXJhdGlvbnMgPSAxMCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxvc3NfZnVuY3Rpb249J0xvZ2xvc3MnLCB2ZXJib3NlPTApKQoKcHJlZF90cmFpbiA8LSBjYXRib29zdC5wcmVkaWN0KG1vZGVsLCBjYXRib29zdC5sb2FkX3Bvb2woWF90cmFpbiksIHByZWRpY3Rpb25fdHlwZSA9ICdQcm9iYWJpbGl0eScpCnByZWRfdGVzdCA8LSBjYXRib29zdC5wcmVkaWN0KG1vZGVsLCBjYXRib29zdC5sb2FkX3Bvb2woWF90ZXN0KSwgcHJlZGljdGlvbl90eXBlID0gJ1Byb2JhYmlsaXR5JykKCmRhdGFfc2hhcF90cmVlIDwtIGNhdGJvb3N0LmdldF9mZWF0dXJlX2ltcG9ydGFuY2UobW9kZWwsIHBvb2wgPSBwb29sLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHR5cGUgPSAiU2hhcFZhbHVlcyIpCmRhdGFfc2hhcF90cmVlIDwtIGRhdGEuZnJhbWUoZGF0YV9zaGFwX3RyZWVbLCAtbmNvbChkYXRhX3NoYXBfdHJlZSldKSAKbmFtZXMoZGF0YV9zaGFwX3RyZWUpID0gbmFtZXMoZGZbLCBjKGNhdF9mZWF0cywgY29udF9mZWF0cyldKQoKCmdncGxvdChzdGFjayhkYXRhX3NoYXBfdHJlZSksIGFlcyh4ID0gaW5kLCB5ID0gdmFsdWVzKSkgKwogICAgZ2VvbV9wb2ludChhZXMoY29sb3IgPSB2YWx1ZXMpKSArIGNvb3JkX2ZsaXAoKSArIGdndGl0bGUoIlNoYXBlbHkgVmFsdWVzIGJ5IHZhcmlhYmxlIikKCnJlc3VsdHNbImNhdGJvb3N0IixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbImNhdGJvb3N0IixdCmBgYAoKYGBge3J9CmZlYXRfaW1wb3J0YW5jZSA8LSBjYXRib29zdC5nZXRfZmVhdHVyZV9pbXBvcnRhbmNlKG1vZGVsLCBwb29sKQppbXBvcnRhbmNlcyA8LSBkYXRhLmZyYW1lKGZlYXRfaW1wb3J0YW5jZVtvcmRlcihmZWF0X2ltcG9ydGFuY2UsIGRlY3JlYXNpbmc9RkFMU0UpLF0pCmltcG9ydGFuY2VzJGZlYXR1cmVzID0gcm93bmFtZXMoaW1wb3J0YW5jZXMpCm5hbWVzKGltcG9ydGFuY2VzKSA8LSBjKCJpbXBvcnRhbmNlIiwiZmVhdHVyZXMiKQppbXBvcnRhbmNlcyRmZWF0dXJlcyA8LSBmYWN0b3IoaW1wb3J0YW5jZXMkZmVhdHVyZXMsIGxldmVsPWltcG9ydGFuY2VzJGZlYXR1cmVzKQpnZ3Bsb3QoaW1wb3J0YW5jZXMsIGFlcyh4PWltcG9ydGFuY2UsIHk9ZmVhdHVyZXMpKSArIGdlb21fYmFyKHN0YXQ9ImlkZW50aXR5IikKYGBgCgojIyBSZXN1bHRzCgpgYGB7cn0KcmVzdWx0cwpyZXN1bHRzW29yZGVyKC1yZXN1bHRzJHRlc3RfYXVjLCAtcmVzdWx0cyR0ZXN0X2FjYyksXQpgYGAKCiMjIEJpYmxpb2dyYXBoeQoKCg==